２分探索法の平均比較回数

[log_2 N]だということはよく聞くんですが、どうやって導出するんでしょうか？

No.1 ベストアンサー 回答者： noname#16258 回答日時： 2004/10/23 13:40

logを計算で出すのではなく、～以上～以内で回数がわかります。

2以内は1回
4以内は2回
8以内は3回
16以内は4回
32以内は5回
64以内は6回
128以内は7回
256以内は8回
512以内は9回
1024以内は10回

例えば800は512以上1024以内なので10回となります。

この回答への補足

それは、最大比較回数[log_2 N]+1を導く議論であるような気がします…。

区間の真ん中の値と比較したときにうまく一致して早めに探索終了してしまうこともあると思うのです。
そのことも考慮した上で、確率やら何やら色々計算して平均比較回数を計算した結果が[log_2 N]であるように思うんですが、それが導けないでいます。m(__)m

補足日時：2004/10/23 13:44