Welcome to Android Central! Were the contacts saved to your Google account, or only the local Phone account? If they were saved to your Google account, then they should have automatically synced to your Google Contacts in the cloud--go to contacts.google.com on your computer browser to see if they're there.
If they were only saved to your local Phone account, then it will be very difficult to retrieve them, since they don't sync anywhere automatically, and are stored in an SQLite database file in a protected system directory.