If you happen to be using macOS, there's mdfind, which uses the spotlight database which is always kept up to date, unlike locate/updatedb, where updatedb is expensive to run, even if you've run it recently.

I have yet to find a good solution for linux CLI... something that uses an internal database that is kept up to date with all directory structure changes.

Maybe someone else has seen something cool for this? :D