昇順に整列された要素数 $n=1024$ の配列に対して2分探索を行うとき、探索に必要な比較回数の最大値はいくつか。

正解：エ　11

解説

正解は「11」です。2分探索は、探索範囲の中央の要素と比較して範囲を半分に絞り込む操作を繰り返します。要素数 $n$ の配列での最大比較回数は $$\lfloor {\log }_{2}n\rfloor +1$$ で求められ、$n=1024=2^{10}$ のとき $10+1=11$ 回です。範囲が1024から1になるまで10回半減し、最後に残った1要素との比較がさらに1回必要になると考えると理解しやすいでしょう。「10」は最後の1回の比較を数え忘れた値です。「512」は範囲を1回絞り込んだ後の要素数で、比較回数ではありません。「1024」は先頭から順に調べる線形探索の最大比較回数です。2分探索の時間計算量は $O(\log n)$ です。

• #計算量
• #探索