Finding Roots Using Binary or Interpolation Search
A binary search algorithm is often used to search for a certain element in a sorted sequence. It can also be used to find a point where a function is zero (if the function is monotonic over the interval, there is one such point).[more]
Instead of dividing the interval, an interpolating search (the secant method) uses linear interpolation to guess where the root might be. This method usually converges faster than a binary search (see Details), but each step is computationally more demanding. This Demonstration provides an interactive graphical comparison of the two methods on a set of example functions.[less]
In general the secant method (interpolation search) converges faster than the binary search. However there are exceptions to this rule, as shown in the cubic example; the binary search converges neatly, whereas the multiple root causes a derivative to be zero, sending the interpolation far away. Such conditions can be very unfortunate for the secant method, but they can be avoided: multiple roots can be eliminated using algebraic methods, like dividing the polynomial by its derivative.