Missing contact records
As far as I know if you did not have the extended logging switched on, if they were permanently deleted there is no direct way to check. 

You might want to compare a backup with the current data, if that is possible?

To reassure you: we work with a fair number of organizations that use CiviCRM, some small and some quite large. None of them have ever experienced contacts simply 'disappearing' from the database.