I wanted to upgrade my system* before I replied to you... I was using 3.18, now I've upgraded to 3.22: search still sucks. Before 3.6 it worked perfectly like I wanted, it emulated my terminal use case - I know there is a a folder named "stuff", so I type "cd s[tab][enter]" and there it, in less than half a second I'm there. With older nautilus I just typed "s[enter]" and there I was, same speed. But not anymore.
And I *did* report to the developers, like the hundreds of others who were sufficiently annoyed to voice their dissatisfaction. We were ignored. Now I rant on random websites, where people make a lot of assumptions about what others did or didn't.
* And now I'm back to fix all the gnome-shell extensions that stopped working, oh joy.