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 x0 = 0, x1 = n-1, and i = 1. Compute the next position with
xi+1 = xi - (v[xi]-k) * (xi - xi-1)/(v[xi] - v[xi-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 <firstname.lastname@example.org> January 2001.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 14 August 2008.
HTML page formatted Fri Mar 25 16:20:35 2011.
Cite this as:
Paul E. Black, "secant search", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 14 August 2008. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/secantSearch.html