Look on Google Contacts. If they're not there, go to More, then to Recover contacts and recover from as far back as you want (up to a month since a contact was deleted.) If they're not there, they weren't Google contacts (the default when you enter a new contact is Device - don't ask me why) and they're gone.