Bisection Method (C++)

Root Finding

The bisection method is a simple and robust root-finding algorithm that repeatedly bisects an interval and selects a subinterval in which a root must lie. 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.