It depends much on what your search criterion is.
If you search for filenames or filename patterns, locate is much faster, but not suitable for freshly generated files, since the index used is normally updated only once per day. But if you can use it, it is super fast.
But with find you can search for file size, file age and other things, which aren't searchable by locate.
If you know where to search, you can use the path to delimit the search scope:
find /some/path -size -10M -size +2M -mtime -365 ...
would only search files from 2 to 10 M, maximum 1 year old in /some/path.
Programs, available in the path can be searched by which, help, lib and configuration files with whereis. Examples:
firefox: /usr/bin/firefox /etc/firefox /usr/lib/firefox /usr/share/firefox /usr/share/man/man1/firefox.1.gz