2分探索（2分探索法）

2分探索（Binary Search）は、整列済みのデータの中央要素と探索値を比較し、候補範囲を半分ずつ捨てて目的の値を探すアルゴリズムです。

■ 試験で押さえるポイント

• 昇順配列では探索値が中央値より小さければ左半分、大きければ右半分へ範囲を更新し、一致又は空範囲になるまで繰り返します。

• 要素数$n$の探索時間は$O(\log_2 n)$で、最大比較回数の目安は$\lfloor\log_2 n\rfloor+1$です。

• ランダムアクセスできる配列に適します。連結リストでは中央要素へ到達する時間が掛かり、利点を得にくくなります。

• 前提は探索キーで整列されていることです。挿入・削除のたびに整列を維持する費用も用途に応じて考慮します。

$T(n)=T\!\left(\frac{n}{2}\right)+O(1)=O(\log_2 n)$

$\text{最大比較回数}=\lfloor\log_2 n\rfloor+1$

■ 選択肢での判断ポイント

2分探索は整列済みデータを前提に、1回の比較で候補をほぼ半分にします。要素数が2倍になっても比較回数はおおむね1回増えるという対数時間を使います。

例: 昇順の15要素なら中央、次の半分、その次の半分と最大4回程度の比較で探索できます。未整列データにはそのまま適用できません。