半分を捨てられる前提
二分探索は、比較結果から探索候補の半分を除外する方法です。昇順の配列で中央の値が目的の値より小さければ、それ以前の値も目的値より小さいので、中央までを候補から外せます。整列していること、または判定が単調であることが根拠です。未整列データへ同じ手順を使っても、捨てた側に目的値があるかもしれません。名前だけを覚えるより、何を根拠に範囲を削れるかを確認します。
挿入位置を例に追う
[2,4,4,7,9]で、4以上が最初に現れる位置を求めます。候補の境界を半開区間[lo,hi)で表し、lo=0、hi=5から始めます。中央が4以上ならhiを中央へ、4未満ならloを中央+1へ動かします。境界が一致した位置1が答えです。等しい値を見つけた時点で直ちに終了する方法では、重複した4のうち最初の位置になる保証はありません。目的を「存在確認」か「境界探索」かに分けます。
| lo | hi | mid | 判定と更新 |
|---|---|---|---|
| 0 | 5 | 2 | 4以上なのでhi=2 |
| 0 | 2 | 1 | 4以上なのでhi=1 |
| 0 | 1 | 0 | 4未満なのでlo=1 |
| 1 | 1 | — | 終了:答え1 |
更新しても保つ性質
下限探索では、loより前はすべて目的値未満、hi以降はすべて目的値以上、という性質を保つように更新できます。配列外の境界hi=nも許し、答えが末尾の次ならnを返します。空配列では最初からlo=hi=0です。中央位置の計算は、固定幅整数ならlo+(hi-lo)/2のように加算のオーバーフローにも配慮します。区間を確実に縮めない更新は、無限ループや境界ずれの原因です。
def lower_bound(values, target):
lo, hi = 0, len(values)
while lo < hi:
mid = lo + (hi - lo) // 2
if values[mid] < target:
lo = mid + 1
else:
hi = mid
return lo比較回数とアクセスの費用
ランダムアクセス可能な配列では、候補数が半減するためO(log n)回の比較と参照で済みます。連結リストのように中央へ進むこと自体が遅い表現では、比較回数が少なくても同じ総時間にはなりません。また、整列配列へ挿入位置を見つけることと、実際に要素を挿入することは別です。位置は二分探索で求められても、順序を保つ挿入には後続要素の移動が必要になる場合があります。
境界を返す実装を実際に追う
下の関数は、target以上となる最初の添字を返します。a=[2,4,4,7,9]、target=4なら、[lo,hi)は[0,5)から[0,2)、[0,1)、[1,1)へ変わり1を返します。各反復の前に、loより左はtarget未満、hi以上はtarget以上という境界が保たれます。target=10ならnを返すので、返り値をそのまま配列へ添字として使ってはいけません。存在確認をしたければ、p<nかつa[p]==targetを別に確認します。空配列でも同じ関数が0を返す点も境界の仕様に含まれます。
def lower_bound(a, target):
lo, hi = 0, len(a)
while lo < hi:
mid = lo + (hi - lo) // 2
if a[mid] < target:
lo = mid + 1
else:
hi = mid
return lo停止条件を不変条件と一緒に試す
ループの長さhi−loは毎回小さくなる必要があります。a[mid]<targetの分岐でlo=midとしてしまうと、一要素の候補区間で変化せず停止しないことがあります。一方の境界を更新した後にmidを以前の値のまま再利用することも誤りです。テストでは配列の先頭より小さい値、末尾より大きい値、同値キーの連続を使い、返り値の左側がすべてtarget未満、右側がすべてtarget以上かを検証できます。具体的な返り値の例だけでなく、この性質で確かめると境界の取り違えを見つけやすくなります。