【アルゴリズム基本】二分探索法

二分探索法(Binary Search)

最近、IT系の資格の勉強やアルゴリズムなど、基本を固めようとしています。
アルゴリズムを勉強する中で、ただコーディングを実装するだけだと忘れてしまいそうなので、忘備録もかねてまとめてみました。

概要

広義単調増加(単調減少)な関数・条件に対して、目的の値や閾値を効率的に見つけるアルゴリズムです。

イメージとしては二分木を根から葉に向かってたどっていく操作に近いです。各ステップで「左に進むか・右に進むか」のどちらか一方にしか進まないため、探索候補の範囲が毎回半分(1/2倍)に絞り込まれていきます。この性質により、計算量は

O(log2 N)

となり、線形探索の O(N) に比べて非常に高速に目的の値へたどり着くことができます。

画像：【アルゴリズム】二分探索法の平均探索回数と近似値より

適用条件(走査対象)

二分探索を適用できる条件は、必ずしも「数値が昇順に並んでいる」ことだけではありません。本質的には、

• ある位置 i に対して条件 P(i) を定義したとき
• j = i + 1 としたとき P(j) >= P(i) が常に成り立つ(単調性がある)

という性質さえ満たしていれば適用可能であって、つまり「あるインデックスを境に、条件を満たさない→満たす、へと単調に切り替わる」構造であれば何でもよいのです。
また、これは数値にも応用することができます。

数値以外への応用例

• 真偽値の探索:[False, False, True, True] を [0, 0, 1, 1] とみなし、はじめて True になる境界(閾値)を探す
• 文字列の探索:文字をバイト列(文字コード)に変換することで大小比較が可能になり、二分探索の対象にできる
• 配列の探索：配列の中で、ある特定の値、あるいはある範囲の最大値ないし最小値を求めることができます。

このように、二分探索は数値の探索に限らず「単調性を持つ判定問題」全般に応用できる、汎用性の高いアルゴリズムであるといえます。

汎用性の高さを実感したエピソードをここで一つ。
CTFに参加した際に、Boolean-based Blind SQL Injectionの手法のなかで二分探索法が登場しました。
データベースの中にある秘匿された文字列の値を割り出すために、文字列をsubstringにより一文字切り出して、それをバイトに変換して二分探索法によって当てるというものです。
こんなところに二分探索法がでてくるのかと大変感銘を受けたことがあります。

「計算量を減らしたい」と考えたときにすぐに頭に思い浮かぶようにしておきたいと感じました。

実装パターン

パターン1: 実数解を求める(誤差を許容する二分探索)

方程式の解など、厳密な整数解ではなく「ある程度の誤差を許容した実数解」を求めたい場合に使います。いわゆる**二分法(bisection method)**による数値計算です。

N = int(input())

def f(x):
    return x**3 + x**2 + 2*x + 3

low = 0
high = N

while high - low > 0.01:
    mid = (low + high) / 2
    if f(mid) > N:
        high = mid
    else:
        low = mid

print((high + low) / 2)

補足・注意点

• この手法が成立するのは、f(x) が探索範囲 [low, high] 内で単調増加(または単調減少)であることが前提です。単調性がない関数に適用すると、正しい解に収束しない可能性があります
• ループの終了条件 high - low > 0.01 の 0.01 は要求される精度によって調整することになります。精度を上げたい場合はこの値を小さくすることになります(その分ループ回数は増える)
• 整数の範囲で解の存在を保証する low, high の初期値を正しく設定する必要があります(今回は 0 と N の間に解があると仮定している)

パターン2: 整数解・リストの探索(lower_bound型)

整数のインデックスや、ソート済みリストの中から「初めて条件を満たす位置」を探す場合に使う典型的な形です。これはいわゆる lower_bound(下限探索) と呼ばれる実装パターン。

target = int(input())
A = list(map(int, input().split()))

low_index = 0
high_index = len(A)

while high_index != low_index:
    mid = (low_index + high_index) // 2
    if A[mid] >= target:
        high_index = mid
    else:
        low_index = mid + 1

print(low_index)  # target 以上となる最初のインデックス

補足・注意点

• mid は必ず整数でなければならないため、// による整数除算(商)を使います
• 実数解のパターン(パターン1)をそのまま整数に適用すると、low と high が隣り合う整数値(差が1)になった時点で mid が常に同じ値を指し続け、無限ループに陥る危険があります。
  これを避けるため、A[mid] < target の場合は low_index に mid ではなく mid + 1 を代入します。これにより探索範囲が確実に狭まり、ループが必ず終了することが保証されるのです。

まとめ

観点	内容
適用条件	単調性(広義単調増加/減少)を持つ探索対象であること
計算量	O(log2 N)
イメージ	二分木を根から辿り、毎回候補を半分に絞り込む
応用範囲	数値だけでなく、真偽値・文字列・最大最小値の探索など幅広い
実装の要点	実数解は二分法、整数解は mid+1 を使ったlower_bound型で無限ループを回避

二分探索は「単調性のある問題を高速に解く」という考え方そのものが重要であり、単純な数値探索以外にも幅広く応用が効く、非常に汎用性の高いアルゴリズムであります。