Pythonで二分探索（バイナリサーチ）を実装する方法｜再帰版・反復版のコード例で解説

はじめに

本記事では、ソート済みリストから特定の要素を効率的に探し出す「二分探索（バイナリサーチ）」について、その基本的な考え方とPythonでの実装方法を解説します。

問題定義

ソートされたリストが与えられます。このリストの中から、指定した要素を二分探索のアルゴリズムを使って見つけ出すことが課題です。

アルゴリズムの流れ

• 探索対象の値 x を、リスト中央の要素と比較します。
• x が中央の要素と一致すれば、そのインデックス（mid）を返します。
• x が中央の要素より大きい場合、x は中央より右側の半分にしか存在し得ないため、右半分を再帰的に探索します。
• x が中央の要素より小さい場合は、左半分を再帰的に探索します。

このように探索範囲が1回ごとに半分になっていくため、計算量は O(log n) となり、線形探索（O(n)）に比べて非常に高速です。

再帰による実装

まずは、関数が自分自身を呼び出す「再帰」を使った実装例です。

def binary_search_recursive(arr, start, end, x):
    # 終了条件のチェック
    if end >= start:
        mid = start + (end - start) // 2

        # 中央の要素と一致した場合
        if arr[mid] == x:
            return mid
        # 中央の要素より小さい場合 → 左半分を探索
        elif arr[mid] > x:
            return binary_search_recursive(arr, start, mid - 1, x)
        # 中央の要素より大きい場合 → 右半分を探索
        else:
            return binary_search_recursive(arr, mid + 1, end, x)
    else:
        # 要素が見つからなかった場合
        return -1

arr = sorted(['t', 'u', 't', 'o', 'r', 'i', 'a', 'l'])
x = 'r'
result = binary_search_recursive(arr, 0, len(arr) - 1, x)

if result != -1:
    print("Element is present at index " + str(result))
else:
    print("Element is not present in array")

反復（ループ）による実装

次に、while文を使った反復型の実装です。再帰呼び出しを行わないため、深い再帰によるスタックオーバーフローを気にせずに済むのが利点です。

def binary_search_iterative(arr, x):
    start = 0
    end = len(arr) - 1

    while start <= end:
        mid = start + (end - start) // 2

        # 中央の要素と一致した場合
        if arr[mid] == x:
            return mid
        # 中央の要素より小さい場合 → 探索範囲を左半分に絞る
        elif arr[mid] > x:
            end = mid - 1
        # 中央の要素より大きい場合 → 探索範囲を右半分に絞る
        else:
            start = mid + 1

    # 要素が見つからなかった場合
    return -1

arr = sorted(['t', 'u', 't', 'o', 'r', 'i', 'a', 'l'])
x = 'r'
result = binary_search_iterative(arr, x)

if result != -1:
    print("Element is present at index " + str(result))
else:
    print("Element is not present in array")

実行結果

Element is present at index 4

ソート後のリストは ['a', 'i', 'l', 'o', 'r', 't', 't', 'u'] となるため、文字 'r' はインデックス4の位置に存在していることが確認できます。

計算量の目安

• 時間計算量： O(log n) — 探索範囲が毎回半分になるため
• 空間計算量： 反復版は O(1)、再帰版は呼び出しスタックの分だけ O(log n)

まとめ

本記事では、二分探索の基本的な仕組みと、Pythonにおける再帰・反復の2つの実装方法を紹介しました。二分探索は大量のデータから高速に目的の値を見つけたい場面で非常に有効なアルゴリズムです。ぜひ自分のコードにも取り入れてみてください。