secant search

(algorithm)

Definition: Search a sorted array by estimating the next position to check based on the values at the two previous positions checked.

See also binary search, interpolation search.

Note: It is called "secant search" because it uses the secant of the function at two successive points to approximate the derivative in the Newton-Raphson formula.

To find a key k in an array v with indexes from 0 to n-1, begin with x₀ = 0, x₁ = n-1, and i = 1. Compute the next position with
x_i+1 = x_i - (v[x_i]-k) * (x_i - x_i-1)/(v[x_i] - v[x_i-1]).
If this lies outside the range, a different method (e.g., midpoint of the range) must be used to get the next position.

Although the theoretical execution time is better than interpolation search or binary search, coding is tricky, and the gains from faster convergence are offset by higher costs per iteration.

Richard Harter <cri@tiac.net> January 2001.

Author: PEB

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 14 August 2008.
HTML page formatted Mon Feb 2 13:10:40 2015.

Cite this as:
Paul E. Black, "secant search", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 14 August 2008. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/secantSearch.html