>>779
ソートされてて数百万件あったらバイナリサーチが速いに決まってる。
ただ、事前に（例えば）千件ごとに抽出したテーブルを作っておいて、そこから探すというなら、SIMD最適化の余地もあるかもしれない。
最適化であって、サーチアルゴリズムと言うわけじゃないけど。
そしてそれでも、キャッシュメモリの効率を考えると、バイナリサーチより速くなるかは疑問だ。
最適化ってのは例えば 32 回とかのループアンロールして、それを SIMD 並列化ね。

あとは、最近検索された結果を覚えておいて、それをソートしておいて、バイナリサーチすることで、事前に範囲を絞り込める。
検索される値に偏りがあるなら平均時間が改善されるだろう。

最後に、データベースがメインメモリになければ SIMD で最適化する余地はほとんどない。
そして本当にメインメモリにあってバイナリサーチしてるのに1秒もかかるなら検索の問題じゃない。プロファイラなどを試すべきだ。
試しに 1GB の float 配列を全探索するとウチの PC で0.5秒位。バイナリサーチなら数マイクロ秒。