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;
}
computed mid = (hi + lo) / 2, but the sum can
overflow on languages without infinite-precision arithmetic, e.g. C++. It is
safer to do mid = lo + (hi - lo) / 2.
When searching in sorted arrays, lo, hi and mid are all integers. When
partitioning the array, one should partition it disjointly, e.g. [lo, mid] and
(mid, hi].
Adapt binary_search to search in a sorted array.
Infinite Loops Due to Precision
References
- Principles of Algorithmic Problem Solving. 10.3 Divide and Conquer > Binary Search. Johan Sannemo. KTH Royal Institute of Technology. www.csc.kth.se . Oct 24, 2018.
- Binary search: an easy but tricky algorithm. Diego Assencio. diego.assencio.com . Jun 29, 2014. Accessed Aug 18, 2022.
In my attempt at writing
binary_search, I had:.. which is equivalent to:
… and doesn’t match ’s.
If
f(mid) == lim, searching in the left half is wrong because we won’t get the largestxsuch thatf(x) <= limcould be in the right half.To quote the poets, check the boundary conditions for your BS.