Search not working in Preview.app

I selected the "Table of Contents" in "View Menu" and searched again. It is working. Check the screenshot:

Anyway, make sure that your PDF contains texts and not the image of some texts.

"BTW, in order to get search working again, you have to close the window (command + w) and reopen on the pdf. Closing Preview all together (command + q) and reopening the pdf doesn't work. This is indeed bizarre." https://discussions.apple.com/message/33927812#33927812

I've selected File->Export as PDF - reopened saved file and the Search worked. Looks like some encoding issue.

For what it's worth: in my case the problem seemed to appear when opening a pdf from Finder. Opening the same file via File>Open in Preview "solves" the problem. Unbelievable something as simple as this is still not fixed in Catalina 🙄