# 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]
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