データ構造とアルゴリズム
配列の中央の要素と比べて、探す範囲を半分ずつに絞っていく二分探索を使うための前提条件として正しいものはどれか。
- Aデータの個数が2のべき乗であること
- Bデータがキーの順に整列されていること
- Cデータに同じ値が含まれていないこと
答えと解説を見る
正解：B. データがキーの順に整列されていること
二分探索は、中央の要素と比べた結果から、目的の値が前半と後半のどちらにあるかを決めて範囲を半分にします。これはデータが整列されているから言えることで、整列されていない配列には使えません。データの個数が2のべき乗でなくても、中央の位置を (下端 + 上端) ÷ 2 の切り捨てなどで決めれば問題なく動きます。同じ値が含まれていても探索はでき、その値のどれか1つが見つかります(最初の位置を求めるには少し工夫が要ります)。
- A. 中央の位置を切り捨てなどで決めれば、個数がいくつでも使えます。
- B. 正しい。整列されているので、中央との比較で前半か後半かを決められます。
- C. 同じ値があっても探索はでき、そのどれかが見つかります。