Login to Gmail online and check the contacts list. If you have been saving them to your Google (Gmail) account - and I *highly* recommend you do - they might still be there and you should be able to just resync them to the phone.
If you have been saving them to Google but now they are gone online also, this will restore them to any point they were at in the last 30 days: