二分探索

用途

二分探索する.

計算量

$O(\log n)$

使い方

dichotomy(探索下限, 探索上限, λ:int -> boolのlambda)でλがtrueになる最小の数が返される.
例えば

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

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

実装

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

Verify

//TODO