正答1
解説
正解は1です。
2分探索は、整列済みのデータの中央の要素と目的の値を比べ、探索範囲を半分ずつ絞り込む方法です。
【選択肢別解説】
1：○ 中央の値との大小で「前半か後半か」を判断するので、データ列が整列されていることが前提です。
整列されていないと、範囲を正しく絞り込めません。
2：× 常に速いわけではありません。
目的のデータが先頭にある場合や、データ数がごく少ない場合は、線形探索の方が早く見つかることがあります。
3：× 探索は先頭からではなく、データ列の中央から始めます。
先頭から順に調べるのは線形探索です。
4：× 比較回数は n log_2 n ではなく、log_2 n に比例します。
n log_2 n は、クイックソートなど高速な整列法の平均計算量です。
【ポイント】
2分探索の最大比較回数はおよそ log_2 n 回、線形探索の平均比較回数はおよそ n/2 回です。
2分探索の前提条件は「データが整列済みであること」です。