二分探索

用途

二分探索する.

計算量

$O(\log n)$

使い方

dichotomy(探索下限, 探索上限, λ:int -> boolのlambda)でλがtrueになる最小の数が返される. 探索範囲は半開区間で渡し, 区間にλがtrueになるものがなかった場合は探索上限値を返す. 例えば

1
2
3
dichotomy(0, 100, [](int n){
  return 50 < n;
});

の返り値は$ 50 < n $を満たす最小のnで51が返される.

実装

1
2
3
4
5
6
int dichotomy(int ng, int ok, const function<bool(int)> &discriminant) {
  ng--;
  while (ok - ng > 1)
    (discriminant((ng + ok) / 2) ? ok : ng) = (ng + ok) / 2;
  return ok;
}

Verify

https://atcoder.jp/contests/typical-algorithm/submissions/59723946