Real-valued binary search

Sometimes the answer is a real number, like 1.41421…, and not a whole number. Then there is no “next candidate” to step to. The window still halves, but it never shrinks to a single point, so you must decide when it is small enough. You also need to remember that computers store real numbers with limited precision.

When the answer is a real number

Suppose we want the number x with x² = 2. On the range [0, 2], x² goes up as x goes up. It is below 2 at x = 0 and above 2 at x = 2, so the answer is somewhere in between. This method is called bisection. It keeps a window that contains the answer and halves it, just like before. The difference is that there is no + 1: the new end of the window is mid itself.

def sqrt_bisect(x, steps=100):
    lo, hi = 0.0, max(1.0, x)
    for _ in range(steps):
        mid = (lo + hi) / 2
        if mid * mid < x:
            lo = mid
        else:
            hi = mid
    return lo

The “settled digits” in the figure are the digits that lo and hi now share. Each step adds about a third of a decimal digit, because log₁₀ 2 ≈ 0.3. So ten halvings give about three more correct digits.

When to stop

After k steps, the window is (hi − lo) / 2^k wide. To make it smaller than a tolerance ε, starting from width W, takes ⌈log₂(W/ε)⌉ steps. Going from width 2 down to 10⁻⁹ takes 31 steps.

So the safest way to stop is to count steps, as the code above does. It is tempting to write a loop like while hi - lo > 1e-17 instead. But that loop can run forever, as the next section explains.

Computer numbers are not exact

A Python float stores about 16 significant digits (53 binary digits). Near 1.414, the gap between one float and the next is about 2.2 × 10⁻¹⁶. When lo and hi are next to each other, (lo + hi) / 2 rounds back to one of them. The window stops shrinking, and hi - lo stays at about 2.2 × 10⁻¹⁶, which is never smaller than 10⁻¹⁷. So the loop never ends.

A fixed count of 100 steps is always enough for a float. After about 60 halvings, lo and hi are neighbouring floats, and the extra steps do no harm.

Limited precision also causes problems with big whole numbers. For big integers, int(math.sqrt(n)) is often wrong, because n is rounded to a float before the square root is taken:

>>> import math
>>> n = 10**30 - 1
>>> int(math.sqrt(n))      # rounded: n became 10**30
1000000000000000
>>> math.isqrt(n)          # exact
999999999999999

Whole-number answers, exactly

When the answer is a whole number, search the whole numbers and avoid floats completely. The square root of n, rounded down, is the largest r with r² ≤ n. The test r * r <= n is true for small r and false for large r, so the answers go T … T F … F. Python’s integers never overflow or round, so the search is exact for any size of n.

This is a search for the last T, which needs one detail that you will see in the next lesson. Python has this built in as math.isqrt. It uses Newton’s method, which is even faster. In the practice problem you build it yourself with binary search, and math.isqrt is switched off.

The general rule: use real-number bisection when the answer is truly continuous, such as a time, an angle or a rate. When the answer is a whole number, or can be made one (for example, counting in paise instead of rupees), search the whole numbers. It is exact, and it always ends.