正答1
解説
正解は1です。
昇順に整列されたデータを2分探索法で探すときの、比較回数の目安を問う問題です。
2分探索法は、探索範囲の中央の値と比べて、範囲を半分ずつに絞り込む方法です。
【計算】
1回の比較で探索範囲は n から n/2 になります。
k 回比較すると、範囲は n/2^k になります。
範囲が1個になるのは n/2^k＝1 のときです。
このとき 2^k＝n なので、k＝log_2 n です。
【選択肢別解説】
1：○ 範囲を半分にする操作を約 log_2 n 回繰り返すと1個に絞り込めるので正しいです。
2：× (log_2 n＋1)／2 は、log_2 n をさらに半分程度にした値です。
2分探索の比較回数を表す式ではありません。
3：× n は、先頭から順に調べる線形探索の最大比較回数です。
2分探索ではこれより大幅に少なくなります。
4：× n^2 は、単純な整列法（バブルソートなど）の比較回数の目安です。
探索の比較回数ではありません。
【ポイント】
例えば n＝1024 なら、2分探索は約10回、線形探索は平均約512回の比較が必要です。
2分探索は「データが整列済みであること」が前提条件です。