二分探索とは？
二分探索（Binary Search）はソート済み配列から特定の値を見つけるアルゴリズムです。各ステップで探索範囲を半分に絞るため、n個の要素から最大log₂(n)回の比較で目的の値を見つけられます。
辞書で単語を調べるとき、最初のページからめくるのではなく、真ん中を開いて前後を判断する——これがまさに二分探索の原理です。
なぜ重要か？
二分探索はコーディングテストで最も頻出するアルゴリズムの一つです。
- •時間計算量: O(log n) — 100万件のデータでも最大20回で探索可能
- •活用範囲: 配列探索、パラメトリック探索、Lower/Upper Bound
- •面接頻出: Google、Amazon、日本の大手IT企業のコーディングテストで必須
動作原理
ステップ1. 配列の中間インデックス（mid）を計算します。
ステップ2. 中間値と探索対象（target）を比較します：
- •target == arr[mid] → 発見
- •target < arr[mid] → 左半分に範囲を縮小
- •target > arr[mid] → 右半分に範囲を縮小
ステップ3. 範囲が空になるまで繰り返します。
時間計算量と空間計算量
| 計算量 | |
|---|---|
| 時間（最良） | O(1) |
| 時間（平均・最悪） | O(log n) |
| 空間（反復） | O(1) |
| 空間（再帰） | O(log n) |
毎回探索範囲が半分になるためO(log n)です。10億件のデータでも約30回の比較で見つけられます。
二分探索の必須条件
配列は必ずソート済みでなければなりません。 未ソートの配列には二分探索を適用できません。ソートが必要な場合は、O(n log n)でソートしてから二分探索を適用します。
面接でよく出る変形
Lower Bound — target以上の最初の位置を見つけます。重複値がある場合に有用です。
Upper Bound — targetを超える最初の位置を見つけます。
パラメトリック探索 — 「条件を満たす最小値・最大値」を二分探索で求めます。「木の切断」「ケーブルの切断」などの問題が典型例です。
よくあるミス
- •mid計算時のオーバーフロー：
(left + right) / 2の代わりにleft + (right - left) / 2を使用 - •無限ループ：left、rightの更新ミスで終了条件に到達しない
- •ソート確認漏れ：二分探索適用前に配列がソート済みか必ず確認
AlgoNoteで直接確認しましょう
二分探索が各ステップでどのように範囲を絞っていくか、AlgoNoteで視覚的に確認できます。配列サイズとtarget値を変えながら実験してみてください。