Fundamental Algorithms8 sections · 291 units
Open in Course

Binary Search on Real Numbers

When the answer is a floating-point value.

Binary search on reals uses precision threshold or fixed iterations.

Example: x\sqrt{x}

function sqrt(x):
    lo = 0, hi = max(1, x)
    for i from 1 to 100:
        mid = (lo + hi) / 2
        if mid * mid < x: lo = mid
        else: hi = mid
    return lo

Why 100100 iterations? Each halves error. After 100100: error <(hi−lo)/2100< (hi-lo)/2^{100}, negligible.

Alternative: while hi - lo > 1e-9. Careful with floating-point comparison.