Bisection: Slow but Guaranteed

Why we hunt for roots at all

A vast amount of computational work eventually boils down to one shape: find an x where f(x) = 0. Where does a projectile hit the ground? Solve height(t) = 0. What interest rate makes a loan's payments balance its principal? Solve a polynomial in the rate equal to zero. Where does supply meet demand, or where does a chemical reaction sit at equilibrium? Each is a place where some function crosses zero. Optimization joins the club too, because a smooth function's minima sit exactly where its derivative vanishes, so minimizing g often means solving g'(x) = 0. Root-finding is the workhorse beneath an enormous range of problems.

The trouble is that almost none of these can be solved with a formula. The quadratic has its tidy formula, and even cubics and quartics have (monstrous) ones, but a famous result says no formula in radicals exists for the general polynomial of degree five or higher. Throw in a sine, an exponential, or a logarithm — as in x = cos(x), or interest-rate equations mixing powers and sums — and there is no closed form at all. So we do what this whole ladder is about: we give up on an exact symbolic answer and instead compute a numerical approximation to the root, as accurate as we care to make it. Every answer in this rung will be approximate, and our real question is always how fast a method drives that approximation toward the truth.

The one promise we can lean on: a sign change

Bisection rests on a single idea so intuitive a child trusts it. Picture a continuous function f drawn without lifting the pen. If at one point a the value f(a) is negative and at another point b the value f(b) is positive, then somewhere between a and b the pen must have crossed the horizontal axis — there must be an x in (a, b) with f(x) = 0. You cannot get from below the line to above it, without touching it, if you never lift the pen. That is the intermediate value theorem put to work: a sign change f(a)*f(b) < 0 across an interval where f is continuous is a guarantee that a root is trapped, or bracketed, inside.

Notice how modest the requirement is. We do not need a formula for f, we do not need its derivative, we do not even need to know where the root is or how many there are — we only need to be able to evaluate f at a point and read off its sign, plus a starting bracket whose endpoints disagree in sign. That modesty is bisection's superpower. Where fancier methods demand derivatives or smoothness or a good initial guess, bisection asks for almost nothing and pays it back with an iron-clad promise.

The algorithm: halve, check the sign, repeat

Given a bracket [a, b] with a sign change, the move is almost embarrassingly simple. Take the midpoint c = (a + b) / 2 and evaluate f(c). Now the root that was somewhere in [a, b] must lie in one of the two halves, and the sign of f(c) tells you which: whichever half still shows a sign change is the one that still brackets the root. Keep that half, throw the other away, and you have a new bracket exactly half as wide that is still guaranteed to contain a root. Repeat. Each step costs just one new evaluation of f and one comparison of signs.

1. Start with a, b such that f(a) and f(b) have opposite signs (so f(a)*f(b) < 0), and pick a tolerance tol for how small the bracket must get.
2. Compute the midpoint c = (a + b) / 2 and evaluate f(c) once.
3. If f(c) is zero (or close enough), c is the root — stop. Otherwise check the sign of f(c).
4. If f(a) and f(c) have opposite signs, the root is in the left half: set b = c. Otherwise it is in the right half: set a = c.
5. If the bracket width b - a is below tol, report the midpoint as the answer; otherwise go back to step 2.

bisection(f, a, b, tol):
    assert f(a) * f(b) < 0          # bracket must show a sign change
    while (b - a) / 2 > tol:
        c = a + (b - a) / 2         # midpoint (this form avoids overflow)
        fc = f(c)
        if fc == 0: return c        # exact hit (rare with floats)
        if f(a) * fc < 0:           # sign change is in the LEFT half
            b = c
        else:                       # sign change is in the RIGHT half
            a = c
    return a + (b - a) / 2          # midpoint of final tiny bracket

How fast — and how slow — it really is

Here is the beautiful, completely predictable part. Every step halves the width of the bracket, and the root is somewhere inside, so the error — the distance from the midpoint to the true root — is at most half the bracket width and is cut in half each iteration. After n steps the initial width has shrunk by a factor of 2^n. Want the answer to a tolerance starting from a bracket of width W? You need about log2(W / tol) steps. To squeeze a bracket of width 1 down to 10^-6 takes about 20 steps; down to 10^-15, near the limit of double precision, takes about 50. Each correct decimal digit costs a fixed roughly 3.3 more steps, forever — no surprises, no acceleration.

That fixed exchange rate is exactly what we mean by linear convergence: the error at the next step is a constant fraction (here one half) of the error now, so e_{n+1} is about (1/2) * e_n. In the language of the convergence rung, bisection has order 1 with an asymptotic constant of 1/2. Compare that with Newton's method, coming later in this rung, whose error squares each step — roughly doubling the number of correct digits per iteration once it gets close. Bisection adds digits one slow trickle at a time; Newton, near a good root, adds them in a flood. By the standards of fast solvers, bisection is genuinely slow, and we should say so plainly.

But slow does not mean weak. Bisection's rate is unconditional: it does not depend on a good starting guess, on the function being smooth, on the derivative behaving, or on anything except that one continuous sign change. Newton can diverge, cycle, or shoot off to infinity from a bad start; bisection literally cannot fail to make progress, because halving an interval that contains a root always shrinks toward that root. It is the one root-finder you can trust to deliver, every time, at a pace you can predict in advance. Slow but guaranteed is not a consolation prize — for many jobs it is exactly the property you want.

Knowing when to stop — and what bisection cannot do

Because bracket width is an honest upper bound on the error, bisection has the cleanest stopping criterion of any root-finder: stop when (b - a)/2 is below your tolerance, and you can certify the error is no larger than that. Most methods cannot make such a guarantee; they can only watch the change between successive guesses and hope it reflects the true error. But two cautions matter. First, choose tolerances relative to the size of the root, not just absolute: pinning a root near 10^6 to an absolute 10^-15 is impossible because that is finer than the spacing between representable doubles there. Second, every numerical answer is an approximation living on the floating-point grid; pushing tol below the unit roundoff just wastes iterations chasing digits the hardware cannot represent.

And there are honest limits to what bisection can find at all. It needs a sign change, so it is blind to roots that touch the axis without crossing — a double root like (x - 2)^2, which dips to zero at x = 2 and bounces back up, never changes sign, so bisection cannot bracket it. It finds only one root inside a given bracket, even if several hide there, and it tells you nothing about complex roots. And in higher dimensions, where you must solve several equations in several unknowns at once, the very notion of 'a sign change across an interval' falls apart; there is no clean multidimensional bisection, which is one reason the later guide on systems reaches for Newton's method instead.