Binary Search

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;
}

In my attempt at writing binary_search, I had:

if (f(mid) > lim) hi = mid; // Search in left half

.. which is equivalent to:

if (lim <= f(mid)) hi = mid; // Search in left half

… and doesn’t match ’s.

If f(mid) == lim, searching in the left half is wrong because we won’t get the largest x such that f(x) <= lim could be in the right half.

To quote the poets, check the boundary conditions for your BS.

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.