整列済み配列の中央の値を調べ、対象があり得る側だけを残します。比較のたびに候補が半分になります。

lo・mid・hiと候補区間の縮小を表示する二分探索シミュレーター

対象値を変更するか、配列の値を選んで再生してください。薄くなったセルは候補から除外済みです。

時間計算量O(log n)

前提条件整列済み配列

100万個最大20回の比較

10億個最大30回の比較

二分探索の3つの形

値の検索は一致した位置で停止します。lower boundはx以上となる最初の位置、upper boundはxより大きい最初の位置を返します。両者の差はxの個数です。「重複が多い」で試してください。Pythonでは bisect_left(a, x)がlower bound、 bisect_right(a, x)がupper boundです。

区間の定義を統一する

この値の検索では閉区間[lo, hi]を使い、条件は lo <= hiです。lower/upper boundでは半開区間[lo, hi)を使い、条件は lo < hiです。定義を混ぜると無限ループや境界のずれが起こります。

パラメトリックサーチ：答えを二分探索する

実現可能な最大値・最小値を探すときは、候補xが実現可能かを判定する関数を用意します。xの増加に対し真偽が一度だけ切り替わるなら、その境界を二分探索できます。ケーブルの切断、木材の切断高さ、ルーターの配置などが例です。

lo, hi = 1, max(a)          # 答えの候補範囲
while lo <= hi:
    mid = (lo + hi) // 2
    if ok(mid):             # midは実現可能
        ans = mid
        lo = mid + 1        # さらに大きい答えを試す
    else:
        hi = mid - 1