平成21年度 春期 午前 問7

✓ これが正解アlog₂n

解説

半分に絞る回数なので対数で表されます。

2 分探索法は、昇順に整列された配列の真ん中と比べて、探したい値がどちら側にあるかを決め、残りを半分に絞ります。これを繰り返すので、対象の個数は n から n の半分、さらにその半分へと減っていき、1 になるまでに何回絞ったかがおよその比較回数になります。ある個数を 1 にするまで半分にし続ける回数は、2 を底とする対数で表されます。したがって比較回数は log₂n におよそ等しくなります。n が 1024 のときは 512 、256 と絞っていくと 10 回で 1 に達し、log₂1024 の値と一致します。n が 100 万に増えても 20 回ほどで済むので、個数が増えても回数がほとんど増えないところがこの方法の強みです。見分けるときの軸は、1 回の比較で対象がどれだけ減るかを読むことです。

ほかの選択肢はなぜ違うのか

• イ(log₂n＋1)／2：半分に絞る考え方から出てくる回数に 1 を足し、それを 2 で割った形です。絞る回数を数える過程には、このように足したり割り直したりする段はありません。
• ウn：先頭から一つずつ順に照合していく探し方の比較回数です。並びが整っているという性質を使わないので、個数がそのまま回数の目安になってしまいます。
• エn²：二重の繰返しですべての組を突き合わせるような処理の手間を表す形で、単純な整列の手順などがこれにあたります。絞り込みの回数を数える流れからは出てきません。