Bisection Method

The bisection method finds an approximate root of a continuous function on an interval. It applies when the function has opposite signs at the two endpoints.

If:

$$ f(l) \cdot f(r) \le 0 $$

and $f$ is continuous, then a root exists somewhere in $[l, r]$.

Problem

Given a continuous function $f$ and an interval $[l, r]$, find a value $x$ such that:

$$ f(x) = 0 $$

In practice, the algorithm returns an approximation whose error is bounded by a chosen tolerance $\varepsilon$.

Key Idea

Use the intermediate value theorem.

At each step:

Compute the midpoint $m$
Evaluate $f(m)$
Keep the half interval where the sign change still occurs

This is binary search over a continuous domain.

Algorithm

bisection_method(f, l, r, eps):
    if f(l) == 0:
        return l
    if f(r) == 0:
        return r

    while r - l > eps:
        m = (l + r) / 2

        if f(m) == 0:
            return m

        if f(l) * f(m) <= 0:
            r = m
        else:
            l = m

    return (l + r) / 2

Example

Find a root of:

$$ f(x) = x^2 - 2 $$

on interval $[1, 2]$.

Since:

$$ f(1) = -1 $$

and

$$ f(2) = 2 $$

there is a root in the interval. Repeated bisection converges to:

$$ \sqrt{2} $$

Correctness

The algorithm maintains the invariant that the current interval contains a root.

Initially, the signs at $l$ and $r$ are opposite or one endpoint is already a root. By continuity, a root exists inside the interval.

At each step, the midpoint divides the interval into two halves. If $f(l)$ and $f(m)$ have opposite signs, then the root lies in $[l, m]$. Otherwise, it lies in $[m, r]$.

The chosen half still satisfies the sign-change condition, so the invariant is preserved.

When the interval length is at most $\varepsilon$, any point inside it approximates a root within that tolerance.

Complexity

Let the initial interval length be:

$$ L = r - l $$

After $k$ iterations, the interval length is:

$$ \frac{L}{2^k} $$

To make this at most $\varepsilon$:

$$ k \ge \log_2 \frac{L}{\varepsilon} $$

cost	value
iterations	$O(\log((r-l)/\varepsilon))$
function evaluations	$O(\log((r-l)/\varepsilon))$
space	$O(1)$

When to Use

Use the bisection method when:

the function is continuous
the interval endpoints have opposite signs
guaranteed convergence matters more than speed
derivative information is unavailable or unreliable

Comparison

method	requires derivative	convergence
bisection	no	guaranteed with sign change
Newton method	yes	fast but may fail
secant method	no	faster but less robust

Notes

Bisection is robust but slower than Newton-style methods.
It finds one root in the interval, not necessarily all roots.
If the function touches zero without changing sign, bisection may not detect it from endpoint signs.
Floating point comparisons to zero should usually use a tolerance.

Implementation

def bisection_method(f, l, r, eps=1e-9):
    fl = f(l)
    fr = f(r)

    if fl == 0:
        return l
    if fr == 0:
        return r
    if fl * fr > 0:
        raise ValueError("f(l) and f(r) must have opposite signs")

    while r - l > eps:
        m = (l + r) / 2
        fm = f(m)

        if fm == 0:
            return m

        if fl * fm <= 0:
            r = m
            fr = fm
        else:
            l = m
            fl = fm

    return (l + r) / 2

import "errors"

func BisectionMethod(f func(float64) float64, l, r, eps float64) (float64, error) {
    fl := f(l)
    fr := f(r)

    if fl == 0 {
        return l, nil
    }
    if fr == 0 {
        return r, nil
    }
    if fl*fr > 0 {
        return 0, errors.New("f(l) and f(r) must have opposite signs")
    }

    for r-l > eps {
        m := (l + r) / 2
        fm := f(m)

        if fm == 0 {
            return m, nil
        }

        if fl*fm <= 0 {
            r = m
            fr = fm
        } else {
            l = m
            fl = fm
        }
    }

    return (l + r) / 2, nil
}