I too like locate (when the file I'm looking for isn't brand spanking new).
Unlike other tools like find(1), locate uses a previously created database to
perform the search, allowing queries to execute much faster. This database is
updated periodically from cron.
May I suggest the mlocate package instead of the locate package.
mlocate instead of re-reading all the contents of all directories each time
the database is updated keeps timestamp information in its database and can
know if the contents of a directory changed without reading them again. This
makes updates much faster and less demanding on the hard drive.