If it was entered as a Google account number (the dropdown at the top when you're adding a new contact), it's at
Google Contacts for30 days. More/Restore contacts. If it was entered as a Device, Phone or SIM contact, it wasn't backed up, so ...
If it hasn't been overwritten yet, it's in a database. The phone has to be rooted, you need a SQLite editor (they're available for free at the Play store)
and you have to be fluent in SQL to find the record you want, change the "deleted" field to false and update the record. Look in the editor, when it's running for a database that sounds like it would have your contacts.