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

Question

ニ分探索法の平均比較回数についての質問です。
例えば、32個のデータから二分探索法で特定の要素を探索する場合、
① 32⇒16
② 16⇒8
③ 8⇒4
④ 4⇒2
⑤ 2⇒1
と5回探せば見つかると思います。
この場合、
5回探せば必ず見つかる一方で、1回目から4回目に見つかる場合もありますよね。
となると、平均比較回数は５より小さいと思ったのですが、参考書を読んでいると平均比較回数は５となっていました。
これはどうしてなのでしょうか？

また、このようにデータ数が丁度２の何乗かになっている場合は、最大比較回数はどうなりますか？

教えていただけると幸いです。

Answer 1

何を検索するかによります。

「その中に必ずあるもの」を探すなら、最大でもlog(N)回で見つかるので平均すればlog(N)より小さいでしょう。

が、「あるかないかわかんないもの」であったら、多くの場合「ない」ことがわかり、そのためにはlog(N)
回の手間がかかりますから。

Comments

[automaker]

ご回答ありがとうございます。
「あるかないかわからないもの」を考えないといけないのですね！勉強になりました！

Answer 2

「確実にあるもの」しか探索対象にしないなら、確かに平均比較回数は5より小さくなります。
しかし、実際に二分探索する場合、「存在しないものがどの場所に入るか」を探すことが多いです。
4回目までで見つかる要素は15しかないのに対し、探索対象は無数にあります。つまり、4回以下で見つかる分に関してはほぼ誤差です。

Comments

[automaker]

ご回答ありがとうございます。
4回以下で見つかる１５のケースが誤差になるほど、「ないもの」を探索するケースが多いということですね！
勉強になりました！