Finding Roots Using Binary or Interpolation Search

Requires a Wolfram Notebook System
Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.
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]
Contributed by: Filip Piekniewski (November 2007)
Open content licensed under CC BY-NC-SA
Snapshots
Details
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.
Permanent Citation
"Finding Roots Using Binary or Interpolation Search"
http://demonstrations.wolfram.com/FindingRootsUsingBinaryOrInterpolationSearch/
Wolfram Demonstrations Project
Published: November 14 2007