データ構造とアルゴリズム
昇順に整列された異なる1,000個の値から二分探索で値を探す。1回の比較で「一致・より小さい・より大きい」が分かるものとすると、見つかる場合も見つからない場合も含めて、比較の回数は最大で何回か。
- A10回
- B32回
- C500回
答えと解説を見る
正解：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) の手間も考える必要があります。
- A. 正しい。2¹⁰ = 1024 ≥ 1000 なので、最大10回で済みます。
- B. √1000 に当たる値で、二分探索の回数とは関係ありません。
- C. 線形探索の平均の回数に近い値です。