O Find não precisa de um índice e percorre o disco toda vez que você o executa. Exemplo
$ find / -name "*mynewprogram*"
localizar e variantes precisam de arquivos de índice, mas eles funcionam - muito mais rápido. 'locate' é do GNU findutils. 'slocate' foi recomendado até o etch; foi uma versão mais 'segura' do locate, os usuários não verão arquivos para os quais não têm acesso. 'mlocate' é recomendado em lenny e mais novo, mlocate tem um mecanismo de indexação mais eficiente.
$ sudo updatedb # to update the index.
$ mlocate mynewprogram
which
pesquisa seu $ PATH para o nome binário que você fornece. Não há necessidade de um índice.
$ which touch
/usr/bin/touch
Se você quiser ver os arquivos instalados de um pacote, use este
dpkg -L coreutils
Para ver qual pacote instalou um arquivo específico
$ dpkg -S /usr/bin/touch
coreutils: /usr/bin/touch