二分探索とは

正解：B. データがキーの順に整列されていること

二分探索は、中央の要素と比べた結果から、目的の値が前半と後半のどちらにあるかを決めて範囲を半分にします。これはデータが整列されているから言えることで、整列されていない配列には使えません。データの個数が2のべき乗でなくても、中央の位置を (下端 + 上端) ÷ 2 の切り捨てなどで決めれば問題なく動きます。同じ値が含まれていても探索はでき、その値のどれか1つが見つかります(最初の位置を求めるには少し工夫が要ります)。

正解：A. 10回

1回の比較で探す範囲がほぼ半分になり、2¹⁰ = 1024 ≥ 1000 なので、最大でも10回で範囲がなくなります(⌊log₂ 1000⌋ + 1 = 10)。計算量は O(log n) で、100万個でも最大20回で済みます。32回は √1000 ≈ 31.6 に当たる値で、500回は線形探索の平均(約 n/2)に近い値です。ただし、二分探索を使うにはデータが整列されている必要があり、整列にかかる O(n log n) の手間も考える必要があります。