Parece que o gnome-search-tool não está disponível no Bionic. No link , ele diz status Excluído.
Eu baixei o deb do repositório Wily Proposed e instalei isso no Bionic e ele funciona muito bem.
Então, por que foi removido? E quais são boas alternativas, especialmente se você quiser uma GUI para procurar por strings (ou regex?) Dentro do conteúdo do arquivo e não apenas dos nomes dos arquivos?