ループ不変条件で二分探索の正しさを示す：重複値を含む自作例

配列 [2, 5, 5, 9, 14, 20] から、9以上になる最初の位置を探します。答えは見れば添字3です。しかし院試の答案で必要なのは、たまたま3に着いた計算記録ではありません。どの昇順配列でも同じ処理が正しい理由です。
院試hubのアルゴリズム対策ページ上部
院試hubの分野ページにある説明と過去問演習への入口です。2026年9月1日取得。画像は入口の存在だけを示し、以下の自作例や証明を裏付けるものではありません。
今回は次の擬似コードを使います。添字は0から始めます。

      lo = -1
hi = n
while hi - lo > 1:
    mid = floor((lo + hi) / 2)
    if a[mid] >= x:
        hi = mid
    else:
        lo = mid
return hi
    

a[-1] と a[n] は実際には読みません。証明だけで使う番兵として a[-1] = -∞、a[n] = +∞ と考えます。

手で追うと3回で止まる

x=9 として状態を並べます。

最後は hi-lo=1 です。返り値3が得られました。途中に5が二つあっても結果は揺れません。

不変条件を一つ決める

反復の前後で次を保ちます。

      a[lo] < x <= a[hi]
    

開始時は番兵により -∞ < x <= +∞ なので成立します。次に保存を見ます。

• a[mid] >= x なら hi=mid とする。新しい右端で x <= a[hi] が成立し、左端は変わらない。
• a[mid] < x なら lo=mid とする。新しい左端で a[lo] < x が成立し、右端は変わらない。
  二つの場合のどちらでも同じ不変条件が残ります。ここが実行例と証明の境目です。

止まったときに最初の位置だと言える理由

ループ中は lo < hi で、更新後の幅は更新前より必ず小さくなります。幅は正の整数なので無限には減りません。やがて hi-lo=1 となって停止します。
停止時も a[lo] < x <= a[hi] は成立しています。lo と hi の間に別の整数添字はありません。したがって hi は x 以上になる最初の位置です。該当要素がなければ番兵の添字 n が返り、仕様とも一致します。

等号の向きは仕様そのもの

もし判定を a[mid] > x に変えると、探すのは「xより大きい最初の位置」です。重複値 [2,5,5,9,9,20] で差が現れます。>= は最初の9、> は9の直後を返します。二分探索の証明で等号を曖昧にすると、コードは動いても別の問題を解いてしまいます。
初期幅は n+1、各反復後の幅は高々ほぼ半分です。したがって反復回数は高々 ceil(log2(n+1)) 回、時間計算量は O(log n)、追加領域は O(1) です。
実際の出題では、擬似コードの穴埋めだけを求める場合も、正当性の説明まで求める場合もあります。東京大学情報理工学系研究科の 入試問題アーカイブ のような大学公式資料で設問の形式を確認するのが先です。科目ごとの入口は InshiHubのアルゴリズム分野ページ にも整理しています。
このMathlog版は、株式会社Fermionが運営するInshiHubの資料を基に、同社が管理する「TeX64 Prime」から公開します。内容の誤りは InshiHubの運営情報・訂正窓口 で受け付けています。