二分探索の仕組み・コード・計算量をわかりやすく解説

二分探索が解決する問題

線形探索は要素を1つずつ調べるため、最大 n 回の比較が必要です。データがソート済みなら、もっと効率よく探せます。目的の値を中央の要素と比べれば、どちらの半分を残せばよいかがすぐにわかります。紙の辞書で単語を引くのと同じ考え方です。

二分探索は配列に限らず、単調なものなら何にでも使えます。ある真偽の条件が小さい値ではすべて偽、大きい値ではすべて真になるなら、二分探索でその境目を見つけられます。これを「答えに対する二分探索」と呼びます。

具体例をステップごとに見る

ソート済みのリスト [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]（インデックス 0〜9）から 23 を探します。まだ調べるべき範囲を挟む2つのインデックス lo と hi を保持します。

線形探索の6回に対して、比較は3回で済みました。100万件のリストでも、二分探索なら最大20回です。

Pythonでの実装

以下の反復版は、閉区間 [lo, hi] を使います。両端とも、まだ候補に含まれます。範囲が空でない間、ループを回します。

def binary_search(items, target):
    lo, hi = 0, len(items) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            lo = mid + 1          # target is in the right half
        else:
            hi = mid - 1          # target is in the left half
    return -1                     # not found
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(data, 23))   # 5
print(binary_search(data, 7))    # -1

実際のPythonコードでは、標準ライブラリの bisect モジュールを使います。bisect_left は、リストのソート順を保ったまま目的の値を挿入できる最も左の位置を返すので、値が存在するかどうかも判定できます。

from bisect import bisect_left, bisect_right, insort
data = [1, 3, 3, 3, 7, 9]
i = bisect_left(data, 3)
print(i, bisect_right(data, 3))   # 1 4  (3 occupies indexes 1..3)
print(i < len(data) and data[i] == 3)   # True: 3 is present
print(bisect_left(data, 5))       # 4: insertion point for 5
insort(data, 5)
print(data)                       # [1, 3, 3, 3, 5, 7, 9]

時間計算量と空間計算量

応用：最初・最後の位置と、答えに対する二分探索

多くの問題では、値が存在するかどうかではなく、境目がどこにあるかが問われます。値が x 以上になる最初のインデックス、x が最後に現れる位置、条件を満たす最小の数などです。半開区間 [lo, hi) を使い、途中で止めないようにします。

def first_true(lo, hi, ok):
    """Smallest x in [lo, hi) with ok(x) True, or hi if none.
    ok must be False...False True...True over the range."""
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid          # mid may be the answer, keep it
        else:
            lo = mid + 1      # mid is too small
    return lo
data = [1, 3, 3, 3, 7, 9]
print(first_true(0, len(data), lambda i: data[i] >= 3))   # 1
# Integer square root of 200: largest x with x*x <= 200
print(first_true(0, 201, lambda x: x * x > 200) - 1)      # 14

• 下限（値が ≥ x となる最初のインデックス）：bisect_left。
• 上限（値が > x となる最初のインデックス）：bisect_right。
• ソート済みリスト中の x の個数：bisect_right(a, x) - bisect_left(a, x)。
• 回転したソート済み配列での探索、ピーク探索、最大値の最小化（例：D日以内にすべての荷物を運べる最小の積載量）は、面接でよく出る定番の応用問題です。

よくある間違い

• 範囲の規約を混在させる。閉区間では lo <= hi と hi = mid - 1、半開区間では lo < hi と hi = mid を使います。混ぜると無限ループや要素の取りこぼしが起こります。
• lo = mid + 1 と書くべきところを lo = mid と書く。hi = lo + 1 のとき mid は lo と等しくなり、ループが終わりません。
• ソートされていないデータに二分探索を使う。エラーも出さずに間違った答えを返します。
• Java、C、C++ のような固定長整数の言語での (lo + hi) / 2 の整数オーバーフロー。lo + (hi - lo) / 2 を使ってください。Pythonの整数はオーバーフローしないので、(lo + hi) // 2 で安全です。
• 重複する値の中で最初の出現位置を求める問題なのに、最初に見つかった一致を返してしまう。

二分探索を使う場面

実際の利用例には、データベースやファイルシステムのインデックス（B木はこの考え方を一般化したものです）、バグを埋め込んだコミットを探す git bisect、IPブロックのような範囲のソート済みテーブルからの値の検索、閾値を探す数多くの数値問題があります。