というか誰かベンチマークとってみたらどうだろう？
>>632の方法と、index-substrと、sort-binsearchのみっつくらいで。
キーの重複はないって条件付きだからそこは悩まなくてもよさ下。