The Bisection Method

Bracket a root between a sign change and halve the interval until it is pinned down - slow but guaranteed.

The guarantee

If f is continuous and f(a) and f(b) have opposite signs, the intermediate value theorem guarantees a root in [a,b]. Bisection exploits this: evaluate the midpoint, keep whichever half still brackets a sign change, and repeat.

def bisect(f,a,b,tol=1e-10):
    fa=f(a)
    while (b-a)/2>tol:
        m=(a+b)/2; fm=f(m)
        if fm==0: return m
        if (fa<0)!=(fm<0): b=m
        else: a,fa=m,fm
    return (a+b)/2
print(bisect(lambda x:x*x-2,1,2))  # 1.41421356...

Convergence rate

Each step halves the interval, so the error falls by a fixed factor of 2 per iteration - linear convergence. To gain one decimal digit you need about 3.3 steps. That is slow compared to Newton, but the progress is completely predictable: after k steps the uncertainty is (b-a)/2^k.

Why keep it

Bisection cannot fail once a bracket is found; it needs no derivative and no good initial guess, only a sign change. That robustness makes it the safety net inside hybrid solvers like Brent's method, which uses fast interpolation steps but reverts to bisection whenever they threaten to leave the bracket.

Practical notes

Finding the initial bracket is the real work - scan for a sign change first. Beware even-multiplicity roots where f touches zero without crossing: there is no sign change, so bisection will not see them. For those, look at the derivative or use a different method.