二分探索は意外と重い

　要素数が少ない配列に対して二分探索を行ってもパフォーマンスは向上しないどころか、微妙に低下することがある。問題設定によっても変わってくるかもしれないが、一般に二分探索では一回のループに3,4回は比較が必要であるのに対し、線形探索なら比較は1回で良い。要素数をnとすると、平均計算量はO(3log(n))とO(n/2)ぐらいか。（二分探索の定数項はもうちょっとまじめに考えんといかんかもしれん。）これがつり合う、つまり3 log n = n / 2となるのはいつぐらいか。もう3年ぐらいまじめに数学をやっていないので、よくわからないのだが、gnuplotで図を描いて調べてみたら、大体n = 17ぐらいだった。つまり、これ以下の要素数しか期待できない場合には、二分探索を使うのは得策では無い。
　実際には定数項はもっとまじめに計算しないといけないだろうし、キャッシュに乗りやすい／乗りにくいといった性質を考慮することも必要かもしれない（要素数が少ないとどちらの場合も問題なくキャッシュに乗るかもしれんが。まぁ、配列の要素サイズによっても変わってくるよね、たぶん。）が、少なくとも、要素が3,4個しかないような場合であれば、二分探索は避けた方がいいと言えると思う。
　なお、二分探索の定数部分が1であったとして、f(x)=log(x) - x / 2 = 0を解くとx=5.7ぐらいのようだ。