>>641, >>646
素朴な疑問なんですが、n 個のデータの並びがランダムなら、
探索に擁する平均の時間計算量は

　線形探索：O(n) = n / 2

　バイナリサーチ:
　　ソーティングに　O(n) = n * log(n)
　　サーチ単体に　　O(n) = log(n)

なのであって、n がどうあろうとも平均的には線形探索が速くありませんでしょうか？？
(データの並びがランダムなら、むしろ線形探索より速度有利なのはハッシュぐらいなのでは？)