It appears the gnome-search-tool is not available in Bionic. On https://launchpad.net/ubuntu/bionic/amd64/gnome-search-tool/3.6.0-2 it says status Deleted.
I've downloaded the deb from Wily Proposed repo and installed that on Bionic and it works just fine.
So why has it been removed? And what are good alternatives, specially if you want a GUI to search for strings (or regex?) inside file content not just file names?
It was removed for being unmaintained, but you can use mate-search-tool instead which is available from the repository and is exactly the same thing.
As an alternative you can use searchmonkey which performs the same task.
I've been using it for awhile now and I like it a lot better because it will show you a preview of how your search phrase is used in each file allowing you to quickly scroll though the resulting files without having to manually open each one up.
As a side note, if you're searching the entire filesystem, searchmonkey gets lost in /proc and takes forever. To solve this I use the find command with -xdev to search only real files in the current filesystem like so: