>>136
logの意味は分かってるんだよね？

log　x　Y = Z なら
xのZ乗 = Y (逆もまた真)

二分探索するデータの総数がNとする。
1回の比較で、探索する範囲は約N/2になる。
(厳密にはN/2または(N-1)/2になる。)
もう1回比較するとさらに半分のN/(2の2乗)になる。
もう1回比較するとさらに半分のN/(2の3乗)になる。
…
そして、いずれ探索する範囲が1になる。

k回比較して1になったとする。
すなわち、N/(2のk乗) ≦ 1
これはk ≦ log2　Nと同じこと。
つまり、比較回数は高々log2　N回。