Searching real numbers

When the answer is a real number, every candidate has neighbours arbitrarily close, so the loop cannot end when lo meets hi. Instead it keeps the invariant (the answer lies in [lo, hi]) and halves the range a fixed number of times. Both updates are simply lo = mid or hi = mid: no ±1, because there is no next candidate.

The test is mid³ ≤ 10 and the range starts at [0, 10]. Each row is the loop run for real.

After eight rounds the range is 10 / 2⁸ ≈ 0.039 wide. Run on, and after 100 rounds lo has settled at 2.154434690032, the cube root of 10 to the precision a double can hold.

A double has 53 significant bits, so between 2²⁹ and 2³⁰ (about 5.4 × 10⁸ to 1.07 × 10⁹) neighbouring doubles are 2⁻²³ ≈ 1.2 × 10⁻⁷ apart. If the answer is near 10⁹ and the loop waits for hi − lo to drop below 10⁻⁹, it never will: once lo and hi are neighbours, mid equals one of them and the range stops shrinking.

A fixed count avoids the question. Each round halves the width, so to get from a width W to a precision ε takes log₂(W / ε) rounds: 10⁹ down to 10⁻⁶ is about 50. A hundred rounds is enough for any double range and costs nothing.

If the precision required is fixed and coarse (prices to the cent, times to the millisecond), scale to integers and use the integer templates instead. Exact arithmetic beats a tolerance.

• Roots of increasing functions: the rate at which an investment reaches a target, the speed at which a schedule just fits. The test is "is f(mid) at least the target?"
• Maximising an average. "The largest average of any subarray of length at least k" has a monotone test: an average of at least m exists exactly when some subarray of a[i] − m of that length has a non-negative sum, which prefix sums check in O(n). Bisection on m wraps it.
• Geometry, such as the time at which two moving points come within a distance, when the distance only decreases and then increases (a different search, on the slope, as in the peaks module).