Finding Roots Using Binary or Interpolation Search

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram CDF Player or other Wolfram Language products.

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

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]

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.



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