Hmm .. I thought it would be an easy fix, too.
Open the Search and Indexing troubleshooter by clicking the
Start button 
and then click
control panel. In the upper right corner is a search box. Type in
troubleshooter and then click
Troubleshooting. Click
View all, and then click
Search and Indexing. This might give you some additional info as to what's wrong with the search function.
You could also see if the search function works in Safe Mode.
Access Safe Mode from Advanced Boot Options (step 3)
See if there are any application conflicts by doing a clean startup (AKA clean boot).
Troubleshoot Application Conflicts by Performing a Clean Startup
Run a full scan with your installed anti-virus suite. Since no anti-malware product is 100% effective 100% of the time you could also double check by running a couple of free on-demand scanners.
Malwarebytes ESET Online Scanner
If nothing works there's always a repair install. But that's really a heavy handed approach for a relatively minor issue (kinda like using a low yield nuclear weapon to kill a fly.) But it would also fix those sfc /scannow errors.
Repair Install
If everything else on your computer is working OK, you might consider using a 3rd party search tool. Both of these are free.
Everything Search Engine Copernic Desktop Search