Finding roots by using bisection is relatively straightforward, although there are a couple of tricky details. One of the most important is realizing that it's not always obvious what interval to use when looking for a root.

For example, if the function's value at the interval's endpoints, x₀ and x₁, are both positive or both negative, then the interval may contain no roots, one root, or several roots. The following diagram shows three functions. All three start and end with function values greater than zero. The curve on the left has no roots because it does not cross the X axis, the middle curve has a single root where it touches the X axis, and the curve on the right has four roots because it crosses the X axis four times:

One way to find roots is to manually pick the intervals that the algorithm should examine. That works, but it requires you to know something about the general shape of the function and the locations of its roots.

The approach I took was to allow you to specify a series of intervals. The program then considers each interval, looking for roots.

The following FindRoots method starts the process:

// Find roots for the equation within the range xmin <= x <= xmax.
private List<double> FindRoots(Func<double, double> F,
    double xmin, double xmax, int numTests,
    double maxError, out List<double> xmins)
{
    xmins = new List<double>();
    List<double> roots = new List<double>();
    double dx = (xmax - xmin) / numTests;
    for (int i = 0; i < numTests; i++)
    {
        double x = xmin + dx * i;
        xmins.Add(x);
        double root = BinarySubdivision(F, x, x + dx, maxError);
        if (!double.IsNaN(root) &&
            !roots.Contains(root, maxError)) roots.Add(root);
    }
    return roots;
}

This method's xmin and xmax parameters define a large range xmin ≤ x ≤ xmax that should contain all of the roots. The numTests parameter indicates the number of intervals into which the program should divide this larger domain to find the roots. The code calculates the size of the intervals and then loops through them, calling the BinarySubdivision method described shortly to look for a root in each interval.

If the BinarySubdivision method returns a number, the FindRoots method calls the Contains extension method to determine whether the root is already in the roots list. The following code shows the Contains method:

public static bool Contains(this List<double> values,
    double target, double maxDiff)
{
    foreach (double value in values)
        if (Math.Abs(value - target) <= maxDiff)
            return true;
    return false;
}

The problem here is that a list of double values might contain two values that should be the same but that are slightly different due to rounding errors. The Contains extension method extends List<double> objects to determine whether the list contains two values that are very close to each other.

The method simply loops through the list, examining items. It subtracts each item from the target value, takes the absolute value, and determines whether the difference is smaller than the maximum allowed difference. The method returns true if the list contains the item and false otherwise.

The following code shows the BinarySubdivision method, which uses binary subdivision to search an interval for a root:

// Search this interval for a root.
private double BinarySubdivision(Func<double, double> F,
    double xmin, double xmax, double maxError)
{
    // Make sure that F(xmin) and F(xmax) have different signs.
    if (Math.Sign(F(xmin)) == Math.Sign(F(xmax)))
        return double.NaN;

    for (;;)
    {
        double x = (xmin + xmax) / 2.0;
        double y = F(x);
        double error = Math.Abs(y);
        if (error < maxError) return x;

        if (Math.Sign(y) == Math.Sign(F(xmin)))
            xmin = x;
        else
            xmax = x;
    }
}

This method verifies that the function has values on opposite sides of the X axis at the two endpoints xmin and xmax. If the function's values at both points are either above or below the X axis, the method returns double.NaN to indicate that it did not find a root.

If the function crosses the X axis, the method enters a loop. Each time it goes through the loop, the program calculates the function's y value at the interval's midpoint x. If y is within maxError of zero, the code returns x as the function's root.

If y is not close enough to zero, the method compares the sign of the function at this point and at xmin. If the two signs are the same, the method moves xmin to the new position x. If the signs of y and F(xmin) are different, then the method updates xmax to the position x.

Eventually, the interval shrinks until y is close enough to zero and the method returns it.

The following screenshot shows the BisectionSubdivisionRoots example solution:

Here the program found the roots for the following equation:

The short vertical lines crossing the X axis in the screenshot show the intervals that the program used to find the roots. In this example, the program used 10 intervals to find the roots.

Download the BisectionRootFinding example solution to see additional details, such as how the program lets you select a function and how it draws the graph of that function.