二分探索 — ソートされたデータの高速検索

このトピックを終えると

二分探索の原理を理解し、O(log n) がなぜ高速なのかを実感し、実際に実装する際の注意点を知ることができます。

辞書で単語を探す

紙の辞書で「Python」を探すとします。最初から順番にページをめくりません。真ん中を開いて「M」であれば奥の方へ、「S」であれば手前の方へ、再び真ん中を開きます。

これが二分探索です。一度見るごとに、探す範囲が半分になります。

線形探索 vs 二分探索

ソートされた 1～100 のリストから 73 を探すとします。

線形探索 — 1, 2, 3, ..., 73。73 回比較する必要があります。

二分探索:

[1 ............... 50 ............... 100] → 50 < 73 → 右側
[51 ......... 75 ......... 100] → 75 > 73 → 左側
[51 .... 63 .... 74] → 63 < 73 → 右側
[64 .. 69 .. 74] → 69 < 73 → 右側
[70 . 72 . 74] → 72 < 73 → 右側
[73] → 見つかった！

6 回で探し出しました。100 個のデータから 73 回 vs 6 回 — すでに 12 倍の差です。

O(log n) の威力

10 億個のデータから、わずか 30 回の比較で答えを見つけます。毎回半分に分割するため、2^30 ≈ 10 億になるからです。

実装

def binary_search(arr, target):
    left = 0
    right = 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  # 見つからない

numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(numbers, 23))  # 5 (インデックス)
print(binary_search(numbers, 10))  # -1 (見つからない)

注意点 3 つ

1. ソートが前提

二分探索は、ソートされたデータでのみ機能します。ソートされていない場合、真ん中の値と比較しても、左側または右側を決定できません。

ソートにかかるコストは O(n log n) です。一度だけ検索する場合は、線形探索 O(n) の方が高速です。二分探索が有効なのは、ソート後に複数回検索する場合です。

2. left <= right (等号)

while left <= right で <= ではなく < と書くと、要素が 1 つ残ったときにチェックをスキップします。最後の 1 つが正しい値である場合に、見つけられません。

3. mid 計算のオーバーフロー

# 安全な計算
mid = left + (right - left) // 2

(left + right) // 2 は Python では問題ありませんが、C/Java など、整数のサイズが固定されている言語では、left + right がオーバーフローする可能性があります。習慣的に上記のように書くのが安全です。

Python 内蔵 — bisect

import bisect

numbers = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

# 挿入位置を検索
idx = bisect.bisect_left(numbers, 23)
print(idx)  # 5

# 値が存在するか確認
if idx < len(numbers) and numbers[idx] == 23:
    print("見つかった")

bisect モジュールは、二分探索を C で実装したものです。自分で実装するよりも高速で、「ソートされたリストに値を挿入する位置」を検索する場合にも使用できます。

重要なポイント

二分探索は、ソートされたデータから毎回半分を破棄するアルゴリズムです。 時間計算量 O(log n) — 10 億個のデータから 30 回で探し出します。 前提条件はソート — 一度ソートした後、複数回検索する場合に効果的です。