| Random Link ¯\_(ツ)_/¯ | ||
| Aug 18, 2022 | » | Binary Search
2 min; updated Sep 5, 2022
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; }... |