“Know how to solve every problem that has been solved.” “What I cannot create, I do not understand.” — Richard Feynman

Bisection Method (C++)

Root Finding

The bisection method finds a root by repeatedly splitting an interval in half and keeping the half that still contains the root. How does it know which half? By sign: if a continuous function is negative at one end and positive at the other, it must cross zero somewhere in between (the intermediate value theorem). Evaluate the midpoint, and whichever half still has ends of opposite sign keeps the root. Each split halves the uncertainty, so after k splits the root is pinned to within (b−a)/2^k. This page shows a C++ implementation.

Algorithm

Given a continuous function $f (x)$ and an interval $[a, b]$ such that $f (a)$ and $f (b)$ have opposite signs, the bisection method:

Computes the midpoint $c = (a + b) /2$
Evaluates $f (c)$
If $f (c) = 0$ or the interval is sufficiently small, return $c$
Otherwise, replace the interval with $[a, c]$ or $[c, b]$ based on which subinterval contains the root

C++ Implementation

The following is a complete C++ implementation with user input:

#include <stdio.h>
#include <math.h>

/* Define the function whose root we want */
double f(double x)
{
    /* Example: f(x) = x^3 - x - 2  (root near x ≈ 1.521) */
    return x*x*x - x - 2.0;
}

int main(void)
{
    double a, b, c;
    double fa, fb, fc;
    double tol;
    int max_iter;
    int iter = 0;

    /* Input */
    printf("Enter left endpoint a: ");
    scanf("%lf", &a);

    printf("Enter right endpoint b: ");
    scanf("%lf", &b);

    printf("Enter tolerance: ");
    scanf("%lf", &tol);

    printf("Enter maximum iterations: ");
    scanf("%d", &max_iter);

    fa = f(a);
    fb = f(b);

    /* Check bracketing condition */
    if (fa * fb > 0.0) {
        printf("Error: f(a) and f(b) must have opposite signs.\n");
        return 1;
    }

    printf("\nIter        a              b              c           f(c)\n");
    printf("----------------------------------------------------------------\n");

    /* Bisection loop */
    while (iter < max_iter) {
        c = 0.5 * (a + b);
        fc = f(c);

        printf("%4d  %14.8f  %14.8f  %14.8f  %14.8f\n",
               iter, a, b, c, fc);

        /* Convergence check */
        if (fabs(fc) < tol || fabs(b - a) < tol) {
            printf("\nConverged to root x = %.10f\n", c);
            return 0;
        }

        /* Update interval */
        if (fa * fc < 0.0) {
            b = c;
            fb = fc;
        } else {
            a = c;
            fa = fc;
        }

        iter++;
    }

    printf("\nMax iterations reached.\n");
    printf("Approximate root x = %.10f\n", c);

    return 0;
}

Key Features

Bracketing check to ensure root exists in interval
Convergence based on function value or interval size
Iteration counter to prevent infinite loops
Detailed output showing progress at each iteration

Convergence

The bisection method converges linearly with rate $1/2$ . After $n$ iterations, the error is bounded by:

∣ x_{n} - x^{*} ∣ \leq \frac{b - a}{2 ^{n}}

where $x^{*}$ is the true root.