アルゴリズム・データ構造図鑑 · 基礎から応用へ

探索の上限を倍々に広げる指数探索

長さを直接取得できない整列列で、終端を含む読取り契約と、最初の一致を返す境界探索を組み立てます。

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

更新日

この記事の目次
  1. 上限が分からない探索を始める
  2. 倍増する位置と残る区間を追う
  3. 最初の一致を返す実装
  4. 費用は見つかる位置へ依存する
  5. 変化する列を検索する場合の限界
  6. 整数の倍増と終端を安全に扱う
  7. 重複区間をまたぐ境界を確認する
  8. 終端に当たった後の課題
  9. この記事をロゲイアに質問する理解を確かめる

上限が分からない探索を始める

整列した列へread(i)でアクセスできますが、長さを直接取得できないとします。存在する位置では値を返し、範囲外ではNoneを返す契約です。探す値を一つ決め、最初の位置を確認した後、位置1、2、4、8と探索の上限を倍々に広げます。探す値以上の値か範囲外へ達したら、答えがあり得る区間が分かるため、その中を二分探索できます。

この方法は、どんな外部サービスにも無制限に大きい添字を投げてよいという意味ではありません。アクセス回数、範囲外の扱い、値の比較可能性を契約へ含めます。Noneを通常のデータ値として使う列では、別の終端表現が必要です。タイムアウトや読取り失敗を範囲外と同じNoneにしてしまうと、まだある列を終端と誤認して答えを捨てる可能性があります。

倍増する位置と残る区間を追う

列を1、3、5、7、9、11、13、15、17とし、目標13を探します。先頭1を確認し、位置1の3、位置2の5、位置4の9までは目標より小さいので次の区間へ進めます。位置8の17で止まり、候補は位置5から8になります。位置4以下は全て9以下なので、もう調べる必要がありません。位置8自体が答えの可能性もあるため、探索区間へ残します。

もし位置8が範囲外でも、終端が位置5と8の間にあるだけで、目標が存在しないとはまだ言えません。二分探索では範囲外を目標以上の側として扱い、左へ境界を寄せます。途中で見つかった小さい値と、右側の大きい値または終端を組にして、答えの候補を閉じ込めます。存在しない値では最後に一致を確かめ、候補位置をそのまま答えとして返さないことが重要です。

読取位置値目標13との関係
01小さい
13小さい
25小さい
49小さい
817上限。位置5〜8を二分探索

最初の一致を返す実装

掲載コードは最初の位置を別に確認します。空ならNone、先頭が目標以上なら、一致するときだけ位置0を返します。その後は、既に小さいと分かった範囲の直後をloにし、hiを二倍に広げます。区間が決まったら、値が目標以上または範囲外ならhiをmidへ、小さければloをmid+1へ更新します。重複する値がある場合も、最初の一致位置へ寄せる契約です。

検査には重複する整列列を使い、長さ0〜39、存在する値と存在しない値を含めてbisect_leftの結果と比較します。readは範囲外で例外を投げずNoneを返す小さな関数です。既存のAPIを使う場合は、そのAPIの範囲外例外だけを明示的に変換し、認証エラーや通信エラーまで終端へ変換しないようにしてください。失敗の分類も探索の正しさへ関わります。

python
from bisect import bisect_left
def search(read,target):
    first=read(0)
    if first is None:return None
    if first>=target:return 0 if first==target else None
    lo=1;hi=1
    while True:
        value=read(hi)
        if value is None or value>=target:break
        lo=hi+1;hi*=2
    while lo<hi:
        mid=(lo+hi)//2;value=read(mid)
        if value is None or value>=target:hi=mid
        else:lo=mid+1
    return lo if read(lo)==target else None
for n in range(40):
    values=[i//2 for i in range(n)]
    def read(i):return values[i] if i<len(values) else None
    for target in range(-1,23):
        i=bisect_left(values,target);expected=i if i<n and values[i]==target else None
        assert search(read,target)==expected
print('empty, first, duplicate, absent and out-of-range cases passed')

費用は見つかる位置へ依存する

答えまたは挿入境界の位置をpとすると、倍増段階はO(log(p+1))回で、見つけた区間の幅もpに比例する範囲へ収まります。二分探索もO(log(p+1))回なので、読取り回数の全体は同じ次数です。先頭や空の列は別に定数回で扱います。列全体の長さが極端に大きくても、目標が先頭近くなら、その長さへ比例して読みに行く必要はありません。

ただし、一回のreadが定数時間という仮定は重要です。連結リストで位置iへ毎回先頭から進むreadを作ると、添字アクセスの数だけを数えて実時間も対数とは言えません。遠隔サービスなら転送量、往復時間、キャッシュ、課金の単位も関係します。アルゴリズムの読取り回数と、アクセス手段が支払う費用を二段階で見積もり、入力形式へ合うかを判断します。

変化する列を検索する場合の限界

探索の途中で列へ要素が挿入され、添字の意味が変わると、前に捨てた区間へ新しい答えが移る場合があります。最初のreadと最後のreadが別の版を見ていれば、整列されている瞬間がそれぞれあっても、一つの安定した列を探した証明は使えません。スナップショットや版番号のある読取りを使うか、更新時の契約を明確にする必要があります。

長さが増え続け、探す値が決して現れず、範囲外にも達しないストリームでは、終了が保証されません。順序のある無限列なら目標を越える値へ到達する条件を考えます。実際の検索サービスでは、最大添字、最大読取り回数、期限を設け、打切りと不在の確定を別の結果として返す方が適切な場合もあります。今回の有限配列向けのNoneという返り値へ、未完了の打切りまで押し込まないでください。

整数の倍増と終端を安全に扱う

Pythonではhiの整数は必要に応じて大きくなりますが、固定幅の添字でhiを二倍にすると桁あふれする可能性があります。符号が反転したり0へ戻ったりすれば、探索区間の拡大や停止の説明が壊れます。最大添字を越える前に飽和させる、上限へ到達したときの最後の区間を処理するなど、使用する型に応じた規則を決めてください。単にunsignedへ変えるだけでは巡回の問題は消えません。

readを呼ぶ回数を減らすなら、直前の値を保存して再利用できます。ただし同じ添字の再読取りが同じ値を返すという契約が前提です。速度の工夫を入れる前に、何を終端とするか、値の比較が全順序か、最初の一致が必要かを確認します。NaNを含む浮動小数点列のように通常の比較が期待どおりの順序を作らない対象では、整列と検索の比較規則を揃える必要があります。

重複区間をまたぐ境界を確認する

目標と同じ値が位置3から7へ並ぶ場合、倍増の位置4で一致を見つけても、最初の一致という契約ではそのまま4を返せません。直前の小さいプローブから4までの区間で左側の境界を探します。単なる存在確認や任意の一件なら、その場で返す別設計もできますが、今回の返り値は最初の添字です。早く見つけたという実装上の都合と、出力へ約束した意味を区別します。

同じ位置を複数回読む実装へ最適化を加えるなら、保存したプローブ値とその位置を対にします。値だけを保存して別の位置の値と取り違えると、区間の証明が壊れます。固定の列で重複と終端を含む検査を使い、返り値の位置が有効で、その前に同値がないことまで確認します。

終端に当たった後の課題

課題は列2、4、6、8、10、12で目標10を探すことです。先頭を確認した後、位置1の4、位置2の6、位置4の10で倍増が止まります。候補区間は位置3〜4で、二分探索を経て位置4を返します。目標を11へ変えると位置4の10も小さいため、位置8で範囲外へ当たり、位置5〜8で境界を探します。位置5は12なので、一致する11は存在しません。

追加課題は列2、2、2、4で目標2を探す場合です。解答は先頭の位置0です。どこか一つの一致でよい仕様なら別の位置でも許せますが、今回のコードは最初の一致という約束を守ります。プローブの値、捨てた範囲、残る区間、最後の一致検査の四点を説明し、範囲外へ当たったことだけで不在と断定していないかを確認してください。

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

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

CS基礎を固める · STEP 10

学習コースから次を選ぶ