Ｈ１１　秋　問１２

２分探索において，整列されているデータの個数が４倍になると，最大探索回数
はどうなるか。

ア　１回増える　イ　２回増える　ウ　約２倍になる　エ　約４倍になる

【解答】　イ
【解説】
ｌｏｇを用いて解説している問題集がありますが，ここでは用いません。

データ１００件と４００件を考える。ここで，電卓テクニックを用いる。

データ１００件の場合。
２×２×・・・。何回目で１００をこえるか。
７回目。これが最大探索回数です。

データ４００件の場合。
２×２×・・・。何回目で４００をこえるか。
９回目。これが最大探索回数です。

（参考）
２＾ｋ　≦　Ｎ　＜　２＾（ｋ＋１）
　　↑　　　　　　　　　　　↑
平均探索回数　　　　　　　最大探索回数
（注）２＾ｋは，２のｋ乗を表す。


（注）ブラウザの戻るボタンをご利用下さい！