女性向けエンジニアスクール
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 つを必ず試します。
似た用語との違い
| 方法 | 前提 | 計算量 |
|---|---|---|
| 線形探索 | なし | O(n) |
| 二分探索 | 整列済み | O(log n) |
| ハッシュ探索 | ハッシュ表を作る | 平均 O(1) |
