二分探索

#Purpose

Performs binary search.

#Time Complexity

$O(\log n)$

#Usage

dichotomy(lower_bound, upper_bound, λ:int -> bool lambda) returns the minimum number for which λ is true. The search range is passed as a half-open interval, and if no evaluation is true within the interval, the upper bound is returned. For example

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

returns 51, which is the minimum n satisfying $50 < n$.

#Implementation

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

#Verify

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