Большая разница в том, что find рекурсивно ищет реальные файлы по заданному каталогу, а locate выполняет поиск в базе данных без необходимости использования определенного каталога. Таким образом, если вы сохранили файл перед обновлением базы данных, find найдет его, но locate не будет.
Что касается whereis и which, они выполняют поиск только внутри этих каталогов которые упоминаются в вашей переменной PATH, и только те, у которых установлен разрешающий набор разрешений