Sharepoint - Is it possible to search the Recycle Bins?

Don't know if there is an OOTB solution for this. I couldn't find one. I was able to find something interesting though. you can search Recycle bin using PowerShell

example : (Get-SPSite "http://SERVERNAME:PORT/").RecycleBin | ?{$_.Title -match "DeletedFile"}

Source

Now you can use c# and PowerShell together and write a custom search solution.