Assencio, Diego

Binary Search on a Non-Decreasing \(f: \mathbb{R} \to \mathbb{R}\)

Given a number \(L\) and a non-decreasing function \(f: \mathbb{R} \to \mathbb{R}\), find the greatest \(x\) such that \(f(x) \le L\). To start, there are two numbers \(lo\) and \(hi\), such that \(f(lo) \le L < f(hi)\).

Algorithm

double binary_search(double lo, double hi, double lim) {
  while (hi - lo > precision) {
    const double mid = (hi + lo) / 2;
    if (lim < f(mid)) hi = mid; // Search in left half
    else lo = mid; // Search in right half
  }
  return lo;
}