In general, I hestiate to recommend a module that I wrote -- and I'm afraid I've been going through an "over-engineering" phase of late -- but if you're interested in File::Locate you might want to at least take a look at the documentation for File::Locate::Harder.

In particular, if you look at the discussion of internals all the way down in the major section titled "NOTES", you'll see a summary of my discoveries in the world of "locate" variants.

Note that if you want to use File::Locate you need to know where your system's "locate" database is stashed, and that varies from system to system and isn't always easily discoverable (it appears to be common for "locate"/"slocate" and "updatedb" to rely on compiled-in defaults that aren't documented in the man pages).