Finding Roots Using Binary or Interpolation Search

Initializing live version
Download to Desktop

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).


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.


Contributed by: Filip Piekniewski (November 2007)
Open content licensed under CC BY-NC-SA



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.

Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.