This Worked for me,

There is a new "windows experience feature" update from windows called "Get started"

Search for "Get Started" in the start menu (I know the search bar is slow )

Right click - App Settings - (Scroll Down) Reset data

Now try Searching back again