2分探索の前提条件として適切なものはどれか。

📝 解説

2分探索（バイナリサーチ）はデータが整列（昇順または降順）されていることを前提に、探索範囲の中央値と目標値を比較して探索範囲を毎回半分に絞り込む高速探索アルゴリズムです。辞書で単語を探すとき、真ん中のページを開いて「目標語が前半か後半か」で残り半分を除外し、また中央を開いて…という作業がまさに2分探索です。1億件のデータでも最大27回（log2(100,000,000)≒27）の比較で見つかります。計算量はO(log n)と非常に効率的です。ただし必ず「整列済みデータ」が前提であり、未整列のデータには使えません。誤答の「データの個数が2のべき乗」という制約はなく（任意の個数で動作）、「リンクリスト構造」は中央値へのアクセスがO(n)かかるため2分探索には不向き（配列・ランダムアクセス可能なデータ構造が適切）、「全てのデータが正の整数」という制約もありません。「2分探索の前提＝整列済みデータ・計算量O(log n)」を確実に覚えましょう！