二分探索 (O(log n))｜コードで実践

二分探索 (O(log n))

このレッスンで分かること

計算量は O(log n)

配列が ソート済み であれば、線形探索よりも圧倒的に速く目的の値を見つけられます

left = 0 、right = n - 1 として、毎回 mid = (left + right) / 2 を計算し、3 通りに分岐します

二分探索 (O(log n)) とは

ソート済み配列に対して中央から半分ずつ範囲を狭める二分探索を実装し、O(log n) の威力を理解する。

配列が ソート済み であれば、線形探索よりも圧倒的に速く目的の値を見つけられます。それが 二分探索 (binary search) です。中央の要素を見て、target がそれより大きいか小さいかで、探索範囲を毎回半分に絞り込みます。

計算量は O(log n) 。n = 1,000,000 のとき、線形探索は最大 100 万 回比較しますが、二分探索はたったの 約 20 回 です (log2(1000000) ≈ 20)。これが「対数時間」のすごさです。

二分探索は ソート済み が大前提。O(log n) で動くため、巨大データでも実質一瞬で見つかる。

アルゴリズムの流れ

left = 0 、right = n - 1 として、毎回 mid = (left + right) / 2 を計算し、3 通りに分岐します。arr[mid] == target なら mid を返し、arr[mid] < target なら左半分を捨てて left = mid + 1 、arr[mid] > target なら右半分を捨てて right = mid - 1 。これを left <= right の間繰り返します。毎回、範囲が半分になるので、n を 1 まで絞り込むには log2(n) 回しかかかりません (n = 1024 なら 10 回、n = 100 万 でも 20 回)。

diagram (will load when visible)

Python での実装例

Python

def binarySearch(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

整数除算 // を使うのがポイントです。Python の / は浮動小数点除算なので、mid がインデックスとして使えなくなります。

JavaScript での実装例

JavaScript

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1;
}

Math.floor で端数を切り捨てます。JS の / は浮動小数点なので Math.floor を忘れないこと。

よくある間違い

1 つ目は 配列がソートされていない ケースで使うこと。二分探索は ソート済み前提 なので、ソートされていない配列に使うと正しく動きません。

2 つ目は 無限ループ 。left = mid や right = mid と書いてしまうと、範囲が縮まずに永遠にループします。必ず left = mid + 1 、right = mid - 1 と書きましょう。

3 つ目は オフバイワン 。while left < right だと最後の 1 要素を見逃します。while left <= right が正解です。配列の 両端を含む閉区間 で考えるとミスが減ります。

Java と Go での実装

Java

public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1
    for left <= right {
        mid := (left + right) / 2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

オーバーフローと応用

mid = (left + right) / 2 は配列の長さが極端に大きいとき、left + right がオーバーフローする可能性があります。Java や C++ では mid = left + (right - left) / 2 と書くのが安全です。Python は整数の上限が事実上ないので問題ありませんが、低レイヤ言語の作法として覚えておくと役立ちます。

二分探索は配列の値を探すだけでなく、「条件を満たす最小の値を探す」用途でも使えます。たとえば「単調増加な関数 f(x) で f(x) >= target を満たす最小の x」は、探索範囲に対する二分探索で O(log n) で解けます。二分探索の答え (binary search on the answer) と呼ばれる発展テクニックで、最適化問題でよく登場します。

O(log n) は「半分ずつ捨てる」アルゴリズムの典型。木構造の高さや累乗計算でも顔を出す。

やってみよう

ソート済み配列 [1, 3, 5, 7, 9, 11, 13] で target = 9 を探すと 4 が返る。
存在しない target = 6 で -1 が返ることを確認する。
n = 1024 の配列で何回のループで見つかるか数えてみる (log2(1024) = 10 回が上限)。

よくある質問

Q. 二分探索の前提は何ですか？

A. 配列がソート済みであることです。未ソートだと結果が保証されません。実行前に Arrays.sort や sorted を呼んでから二分探索するか、最初からソート済みのデータ構造（TreeSet / SortedDict）を使ってください。

Q. 再帰版と反復版はどっちが良いですか？

A. 反復版が安定して高速です。再帰版は読みやすい代わりにスタック消費があります。配列の長さが極端に大きい（数億）場合のみ反復版を選び、教育用や読みやすさ重視なら再帰版で十分です。Python は再帰深さ制限にも注意してください。

Q. lower_bound / upper_bound とは何ですか？

A. lower_bound は target 以上が最初に現れる位置、upper_bound は target より大きい値が最初に現れる位置を返します。重複要素のある配列で「何個含まれているか」を upper - lower で求める典型イディオムで使います。

次のレッスン

次は バブルソート に進みましょう。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

二分探索の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. 二分探索とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

二分探索 (O(log n))