Run cmd.exe as Administrator and execute the following command:
When your search doesn't work and Windows troubleshooting says the permissions are wrong, but cannot fix it, run the following command to fix the permissions and your search probably works, again (immediately).
takeown.exe /R /F C:\ProgramData\Microsoft\Search\
if it still doesn't work run
takeown.exe /R /F C:\ProgramData\Microsoft\