The search button should be at the very top of the parts window, right below the “Parts” title text. Do you see part icons in the parts window? If not, the parts library probably never finished downloading. It is supposed to automatically download the first time you run Fritzing after installing. But it takes time, and if aborted (say by closing Fritzing), it might never complete. With no parts library, perhaps the search icon never shows up.
In this screenshot, the default when I start Fritzing, the “core” parts bin is active (displayed). You need to click the circled magnifying glass to get search.
The bottom of the icons in the parts windows has scroll buttons. You may need to use those, or the scrollbar on the right to get to the the top and the search icon. That image is the what Fritzing looks like when started without a sketch/document. If opened with a sketch file, the view adjust depending if the sketch includes custom parts that are not in the library.