二分探索の実装と応用

「たくさん並んだデータから、欲しい値を素早く見つけたい」。 そんなとき、毎回先頭から順番に探していては時間がかかってしまいますよね。そこで登場するのが二分探索です。

これは、辞書で単語を探すときに最初から1ページずつめくらず、真ん中あたりを開いて「あ、まだ先だな」「いや、戻ろう」とページを半分ずつ絞り込んでいく、あの感覚にとても近いアルゴリズムです。

線形探索が「1つずつ調べる」のに対して、二分探索は「毎回ちょうど半分を捨てる」ため、時間計算量が O(log n) と非常に効率的です。大きなデータになればなるほど、その差は劇的に大きくなります。

今回は、Pythonでの実装からよくある落とし穴、便利な応用例まで、IT初心者の方にもやさしく丁寧に解説します。

二分探索の基本

まずは全体像をつかみましょう。ここでは、アルゴリズムの進み方をイメージしやすいように手順を整理します。

• 二分探索はソート済みのリストが前提です。ここが崩れると正しく動きません。
• 探索のたびに中央を確かめ、必要のない半分を捨てることを繰り返します。

次に、操作の流れを順に追っていきましょう。

1. リストの中央の要素を調べます。
2. その要素が探している値と一致すれば終了です。
3. 一致しない場合、探している値が中央より小さいか大きいかで、探索範囲を左半分または右半分に絞ります。
4. 絞り込みを繰り返し、要素が見つかるか、範囲がなくなるまで続けます。

「なぜ速いの？」と気になりますよね。毎回探索範囲が半分になるので、必要なステップ数はデータ数 n に対して「2で割っていく回数」、つまりおおよそ log2 n 回で済みます。100万件でも20回ほどの比較で見つけられると聞くと、効率の良さが実感できるはずです。

サンプルコード

ここからはPythonで動かせるコードを見て、二分探索の感覚をつかみましょう。

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            right = mid - 1
        else:
            left = mid + 1

    return -1

arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 7
result = binary_search(arr, target)
print(result)  # 出力は 3

この関数は、あらかじめ昇順にソートされたリスト arr の中から target を探し、そのインデックスを返します。見つからなければ -1 を返します。

処理の要は3つです。まず、探索範囲を示す left と right を配列の両端に置きます。次に、範囲の中央を mid として計算し、arr[mid] と target を比較します。等しければその場で見つかった位置 mid を返して終了です。一致しない場合は、arr[mid] が大きいか小さいかで「右端を mid-1 に寄せる」または「左端を mid+1 に寄せる」ことで、不要な半分を丸ごと捨てます。

これを範囲がなくなる（left > right になる）まで繰り返す、という流れです。mid の計算式 left + (right - left) // 2 は、他言語でのオーバーフロー回避の定番テクニックで、Pythonでは整数が自動で大きくなるため問題になりにくいものの、習慣として覚えておくと良いでしょう。

この例では、7 はインデックス 3 にあります。中央を見て半分ずつ絞っていく動きが、頭の中でイメージできたでしょうか。「本当にそんなに速いの？」と思った方は、同じ配列に対して最初から順番に探す線形探索と比較してみると、ステップ数の違いが実感できます。

二分探索の応用

「ぴったり一致を探す」だけが二分探索ではありません。判定が単調（左から右へ進むと、ある地点を境にFalseからTrueへ一方向に切り替わる）な問題なら、多くが二分探索で解けます。

例えば「target より大きい最小の要素」や「target 以上が初めて現れる位置」などが定番です。

例題: 指定値より大きい最小の要素を探す

ここでは、半開区間スタイルで「target より大きい最小の要素の位置」を探します。見つからなければ -1 を返します。

def find_min_greater_than(arr, target):
    left, right = 0, len(arr)

    while left < right:
        mid = left + (right - left) // 2

        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid

    return left if left < len(arr) else -1

arr = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
target = 7
result = find_min_greater_than(arr, target)
print(result)        # 出力: 3
print(arr[result])   # 出力: 8

このコードでは、探索範囲を [left, right) として扱い、常に「条件を満たす可能性がある側」を残すように左右を狭めています。arr[mid] が target 以下であれば「左側はすべて条件を満たさない」ため left を mid+1 に進めます。逆に target より大きければ、その mid も候補なので右端を mid に寄せて、より左側にあるかもしれない最小の候補を探しにいきます。ループが終わったとき、left は「初めて条件を満たす位置」を指します。配列の範囲外でなければそれが答えです。

この場合、target=7 より大きい最小の要素は 8 で、その位置はインデックス 3 です。「target 以上の最小位置（lower_bound）」や「target より大きい最小位置（upper_bound）」といった言い回しも、二分探索ではよく使われます。

標準ライブラリ bisect を使う

「自分で毎回二分探索を書くのは不安…」という方に朗報です。Pythonには bisect という標準ライブラリがあり、二分探索の典型操作（挿入位置の検索）を安全に行えます。まずは簡単な導入から見ていきましょう。

import bisect

arr = [2, 4, 6, 8, 10]

# target と等しい要素を探す（あればインデックス、なければ -1）
target = 8
i = bisect.bisect_left(arr, target)
idx = i if i < len(arr) and arr[i] == target else -1
print(idx)  # 3

# target より大きい最小の位置（挿入位置）
j = bisect.bisect_right(arr, 8)
print(j)    # 4  → arr[4] は 10（8 より大きい最小の要素）

bisect を使うと、境界のバグ（オフバイワン）を避けやすくなり、読みやすいコードになります。まずはこの標準ライブラリを使い、仕組みに慣れてから自前実装に挑戦するのも良い流れです。

まとめ

二分探索は「半分に絞る」を繰り返すだけの、とてもシンプルで強力なテクニックです。Pythonでは while ループで読みやすく書けるほか、標準ライブラリ bisect を使えば境界探索も短く安全に実装できます。重要なのは、データがソートされていること、範囲の扱い（閉区間か半開区間か）をブレずに書くこと、そして要件に合った戻り値の仕様を最初に決めることです。

「一致を探す」「境界を探す」「真偽が単調に切り替わる条件の最小/最大を探す」——二分探索の応用先はとても広いです。

次のステップでは、線形探索や時間計算量の基礎とあわせて、「どの場面で二分探索を選ぶべきか」を判断できるようになることを目指しましょう。