por ahí conviene utilizar locate junto con updatedb.
Primero corres updatedb, se crea una lista de lo que hay en tu sistema, luego con locate buscas el archivo.
Te recomiendo que agregues updatedb al cron para que corra cada x cantidad de tiempo en un horario que no utilices el sistema, de todas formas no merma el rendimiento del sistema, pero de esta forma tendrías siempre actualizado la lista de ficheros de tu equipo.
Saludos
Un ejemplo de uso del comando find de linux:
find -name miarchivo.gif
Eso busca un archivo llamado miarchivo.gif en el directorio actual y todos los subdirectorios.
find -name miarchivo.*
Esto busca un fichero llamado miarchivo, que tenga cualquier extension.