There are a lot of answers floating around, after reading a bunch of stuff the problem seems to be something like corrupt database/permission issues or something of that sort.
So make it easy just create a new folder search (outside of the usual area… programdata) like maybe c:\temp\search
Use the Index rebuilding tool from Control Panel to move the location of the search folder…. restart the computer.
If you are not comfortable changing this location, just do one more step before restarting… move the location back to c:\programdata\microsoft and then restart the computer.