パッケージ名がlocateではなく、mlocateなので注意。

インストール後、updatedbを実行するとlocateが使えるようになる。