例題 : 長さ $N$ の非負整数列 $A$ の中で 非負整数 $X$ 以上 で最小の数を答えろ.

$$ N \le 10^5 \times 2 \\ 全ての i (1\le i \le n) において0 < A_i \le 10^{16} \\ 0 \le X \le \mathrm{max}(A_i) \\ Aは昇順 $$

実装面について

この問題自体はlower_bound()で解答が求められるが,整数列以外でも色々な応用がきく二分探索の実装について考える.

数直線をイメージして変数 l , r を持つことがほとんど.

l をありうる最小値(よりも低い値), rをありうる最大値(よりも大きい値)で初期化する.

例題では添字をlとrに持って二分探索するのが一般的である.

$$ \mathrm{mid} = (l+r) / 2 $$

として定義しmidが添字のとき,条件を満たしたら r = mid , 満たさなかったら l = mid と代入し探索範囲を狭めていく.

この例題では 満たす場合は r = mid としているが本質的には

条件を満たす境界が [l , mid) にあるか [mid , r)にあるかを考え,前者ならば rにmidを,後者ならばlにmidを代入する

([l , mid) の範囲は必ず条件を満たすことが保証されるのでれば[mid,r)の範囲を探索するべき,ということ.)

ということである.

二分探索ではある値を境に条件を満たすことが前提のデータ構造に対して行うことが前提である.

制約より,lとrではA[r]のほうが値が大きく,A[mid]が条件を満たしているのならばA[r]も条件を満たしていることは自明であるのでmidをrに代入しても問題ない.

逆にA[mid]が条件を満たしていない場合はA[mid]からA[r]の間で条件を満たしている値が存在しないことと同値であるためA[mid]からA[r]の間を探索するべきである.なのでlにmidを代入する.

以上を踏まえた実装コード(本質部分のみ)

	  int l = 0;
    int r = n-1;
    while(r-l > 1){
        int mid = (l+r) / 2;
        if(a[mid]>=x) r = mid;
        else l = mid;
    }
    cout<<a[r]<<endl;