このページの目次

二分探索とは？

最終更新：2026/08/18

3秒でわかる

整列済みのデータの中央と比べ、半分ずつ候補を捨てながら目的の値を探す方法。100万件でも20回ほどの比較で目的の位置にたどり着けます。

もう少し詳しく

どういうものか

二分探索は、あらかじめ並べ替えられたデータの真ん中を見て、探している値がそれより大きいか小さいかを判断し、片側を丸ごと捨てる操作を繰り返す探索方法です。1 回の比較で候補が半分になるため、100 万件でも 20 回ほど、10 億件でも 30 回ほどの比較で目的の位置にたどり着きます。

なぜ必要か

先頭から順に見ていく線形探索は、件数が 10 倍になれば時間も 10 倍になります。二分探索は 10 倍になっても比較回数が 3 回ちょっと増えるだけです。この差は件数が大きいほど効き、データベースのインデックスや、辞書引き、コミット履歴から不具合の混入地点を探す git bisect まで、同じ考え方が広く使われています。前提として並べ替えが要る点だけが条件です。

具体例

def binary_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

data = [3, 8, 12, 19, 24, 31, 47]
print(binary_search(data, 24))  # 4

探索の様子は下のとおりです。

[3, 8, 12, 19, 24, 31, 47]  中央19 -> 24は右
             [24, 31, 47]   中央31 -> 24は左
             [24]           一致

つまずきやすいところ

無限ループがもっとも多い失敗です。lo = mid と書くと候補が減らない場合があり、必ず mid + 1 と mid - 1 にします。条件を lo < hi にすると候補が 1 個になった時点で調べずに終わるため、要素 1 個の配列で見つからない不具合になります。そして最大の前提の見落としが並べ替えで、未整列のデータに対しても実行はでき、エラーも出ないまま「見つからない」と返します。境界の確認は、要素 0 個、1 個、先頭、末尾の 4 つを必ず試します。