We’ve already met Bisection Search as a way to search a sorted list. The same halving idea can be used to solve equations of the form \(f(x) = 0\) for a continuous function \(f\text{:}\) this is the bisection method.
Suppose we know that a solution lies somewhere between \(x=a\) and \(x=b\) (that is, \(f(a)\) and \(f(b)\) have opposite signs). We compute the midpoint \(x_1 = (a+b)/2\text{,}\) and check the sign of \(f(x_1)\text{:}\) if it has the same sign as \(f(a)\text{,}\) the root must be between \(x_1\) and \(b\text{,}\) so we replace \(a\) with \(x_1\text{.}\) Otherwise, the root is between \(a\) and \(x_1\text{,}\) so we replace \(b\) with \(x_1\text{.}\) Either way, we now have a shorter interval containing the root, and we repeat the process until the interval is “short enough”.
Populate two arrays with the \(x\) and \(y\) coordinates over the interval \([a,b] = [2.0, 4.0]\text{,}\) and plot them using gnuplot, as in the previous section.
Compute a first estimate \(x_1 = (a+b)/2\text{.}\) Determine whether the true solution lies between \(a\) and \(x_1\text{,}\) or between \(x_1\) and \(b\text{,}\) by comparing the signs of \(f(a)\text{,}\)\(f(x_1)\text{,}\) and \(f(b)\text{,}\) then replace \(a\) or \(b\) with \(x_1\) to obtain a shorter interval that still contains the solution, and repeat.
