How to find if a Site Collection is deleted in SharePoint Online

You can do that from the UI, from SharePoint Admin Center. Navigate to your Admin center and on the ribbon, you should see the recycle bin where you can find any deleted site collections.

--------EXAMPLE 1--------

Get-SPODeletedSite -Identity http://contoso.sharepoint.com/sites/marketing

This example returns the properties for the deleted site collection http://contoso.sharepoint.com/sites/marketing that is in the Recycle Bin.

--------EXAMPLE 2--------

Get-SPODeletedSite -IncludePersonalSite

This example returns all of the properties for the deleted sites, including Personal Sites, that are in the Recycle Bin.

--------EXAMPLE 3--------

Get-SPODeletedSite - IncludeOnlyPersonalSite

This example returns all of the properties for only the Personal sites, that are in the Recycle Bin.