実験・実装 · 基礎から応用へ

二分探索の不変条件をテストする

小さい整列列を網羅し、境界の更新と重複・空配列の扱いを不変条件で確かめる。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 探すものを最初に定義する
  2. 不変条件をコードで確認する
  3. 4158件の小さい入力を試す
  4. 試験と証明をつなぐ
  5. この記事をロゲイアに質問する理解を確かめる

探すものを最初に定義する

Python 3で、整列した列からtarget以上となる最初の位置を返すlower_boundを実装します。値が存在するかだけを返す探索とは、戻り値の意味が違います。重複がある場合は左端、すべて小さい場合は列の長さ、空列では0です。配列内の値を並べ替えず、半開区間[lo,hi)を候補として保ちます。入力が整列済みという前提を外すと、この探索の正しさは保証されません。

不変条件をコードで確認する

loより左はすべてtarget未満、hi以降はすべてtarget以上という条件を、各反復の前後でassertします。中央の値がtarget未満なら、中央自身も答えではないためloをmid+1へ進めます。それ以外なら中央が答えの候補なのでhiをmidへ戻します。mid-1にすると答えを除外する場合があります。このコードでは不変条件の検査にスライス走査を使うため、実行全体の計算量を通常のO(log n)探索と同じだと説明してはいけません。

python
from itertools import combinations_with_replacement
from bisect import bisect_left
def lower_bound(a, target):
    lo, hi = 0, len(a)
    while lo < hi:
        assert all(x < target for x in a[:lo])
        assert all(x >= target for x in a[hi:])
        mid = lo + (hi-lo)//2
        if a[mid] < target: lo = mid+1
        else: hi = mid
    assert all(x < target for x in a[:lo])
    assert all(x >= target for x in a[lo:])
    return lo
cases=0
for length in range(7):
    for values in combinations_with_replacement(range(-2,3),length):
        for target in range(-4,5):
            assert lower_bound(values,target) == bisect_left(values,target)
            cases += 1
print("cases", cases)
assert cases == 4158

4158件の小さい入力を試す

長さ0から6、要素-2から2の整列列を重複込みですべて列挙し、targetを-4から4まで変えます。合計4158件について、Python標準のbisect_leftと結果を比較します。空列、最初や最後の位置、全要素が同じ列、範囲外のtargetが含まれます。偶然の乱数だけに頼らず、小さい境界ケースを再現できるのが利点です。一方、標準関数との一致だけでなく、不変条件も検査することで戻り値の意味を直接確認します。

試験と証明をつなぐ

すべての有限ケースを試したという意味ではなく、小さい範囲を網羅した結果です。一般の正しさには、初期状態で不変条件が成立すること、各分岐がそれを保つこと、区間幅が減って停止すること、停止時に求める位置が得られることを説明します。実用版ではassert用の全走査を外し、比較回数の増え方を別途測ります。浮動小数点のNaNや、通常と異なる比較関数では整列関係の前提も再確認してください。

境界探索のテストで、要素が見つかった位置ならどこでも正解とすると重複時の誤りを逃します。戻り値の前はすべてtarget未満で、戻り値以降はすべてtarget以上という仕様をそのまま検査します。入力にない値の挿入位置も同じ規則で確かめられます。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 10

学習コースから次を選ぶ