アルゴリズム・データ構造図鑑 · 入門

二分探索:半開区間と不変条件で境界を扱う

整列済み配列から候補を半分ずつ除外し、重複や挿入位置まで正しく扱う。

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

更新日

この記事の目次
  1. 半分を捨てられる前提
  2. 挿入位置を例に追う
  3. 更新しても保つ性質
  4. 比較回数とアクセスの費用
  5. 境界を返す実装を実際に追う
  6. 停止条件を不変条件と一緒に試す
  7. この記事をロゲイアに質問する理解を確かめる

半分を捨てられる前提

二分探索は、比較結果から探索候補の半分を除外する方法です。昇順の配列で中央の値が目的の値より小さければ、それ以前の値も目的値より小さいので、中央までを候補から外せます。整列していること、または判定が単調であることが根拠です。未整列データへ同じ手順を使っても、捨てた側に目的値があるかもしれません。名前だけを覚えるより、何を根拠に範囲を削れるかを確認します。

挿入位置を例に追う

[2,4,4,7,9]で、4以上が最初に現れる位置を求めます。候補の境界を半開区間[lo,hi)で表し、lo=0、hi=5から始めます。中央が4以上ならhiを中央へ、4未満ならloを中央+1へ動かします。境界が一致した位置1が答えです。等しい値を見つけた時点で直ちに終了する方法では、重複した4のうち最初の位置になる保証はありません。目的を「存在確認」か「境界探索」かに分けます。

lohimid判定と更新
0524以上なのでhi=2
0214以上なのでhi=1
0104未満なのでlo=1
11—終了:答え1

更新しても保つ性質

下限探索では、loより前はすべて目的値未満、hi以降はすべて目的値以上、という性質を保つように更新できます。配列外の境界hi=nも許し、答えが末尾の次ならnを返します。空配列では最初からlo=hi=0です。中央位置の計算は、固定幅整数ならlo+(hi-lo)/2のように加算のオーバーフローにも配慮します。区間を確実に縮めない更新は、無限ループや境界ずれの原因です。

python
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を返す点も境界の仕様に含まれます。

Python
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以上かを検証できます。具体的な返り値の例だけでなく、この性質で確かめると境界の取り違えを見つけやすくなります。

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

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

CS基礎を固める · STEP 10

学習コースから次を選ぶ