Numeric binary search

Keep lo and hi such that the answer is always between them. Take mid = (lo + hi) / 2, test it, and replace either lo or hi with mid. Unlike the integer version there is no + 1, because there is no next value to step to.

Change the epsilon in the animation and see how the number of iterations grows.

1public static double sqrt(double x, double eps) {
2    double lo = 0, hi = Math.max(1, x);
3    while (hi - lo > eps) {
4        double mid = (lo + hi) / 2;
5        if (mid * mid < x) {
6            lo = mid;
7        } else {
8            hi = mid;
9        }
10    }
11    return (lo + hi) / 2;
12}

Stopping when hi - lo <= eps guarantees the returned midpoint is within eps / 2 of the true answer. Each iteration halves the width, so it takes about log₂((hi - lo) / eps) steps.

An absolute epsilon breaks down at extreme magnitudes: 1e-9 is too strict for values near 1e12 (doubles cannot even represent that gap) and too loose for values near 1e-12.

The test inside the loop must be monotonic even in floating point. mid * mid < x is safe; comparing doubles for exact equality is not.

When the predicate is expensive or noisy, or precision near the boundary is limited, use a fixed number of iterations instead of an epsilon. One hundred halvings shrink the interval by 2^100 ≈ 10^30, which is more precision than a double holds for the ranges met in practice.

1double lo = 0, hi = Math.max(1, x);
2for (int iter = 0; iter < 100; iter++) {     // fixed count: always terminates
3    double mid = (lo + hi) / 2;
4    if (mid * mid < x) lo = mid;
5    else hi = mid;
6}
7return (lo + hi) / 2;

Any monotonic real function can be inverted this way. Examples: the smallest time t at which a moving object reaches a distance, the interest rate that hits a target balance, or the cube root of a number.

For continuous optimisation of a unimodal function, the same shrinking-interval idea becomes ternary search, covered in the next lesson.

• Bound the range first. Doubling hi until the predicate flips works when no upper bound is known.
• Print with fixed precision (e.g. String.format("%.6f", ans)) to match judge output.