The Unity search menu was really frustrating. It had confusing category buttons, and if you did a search that only had results in a specific category, it would inexplicably turn on that category filter and use it for future searches too until you cleared the textbox. I loved pretty much everything about Unity except for that baffling bit. I'm almost glad they're killing Unity just so it means people aren't subjected to that wacky design decision or bug.
Not at my computer, so can't provide a detailed answer yet. It's GNOME something-or-other though. Not Unity. And the menu is question that just works is accessible from something like Alt-F2 or the super key (it's muscle memory and I'd need to be at a keyboard to say for sure).
KRunner on Kubuntu os a joy to use.
Now I use dmenu in i3wm and I couldn't be happier. All I need is something that searches my path for applications... and that's what it does.