(algorithm)
Definition: Search a sorted array by narrowing possible locations to progressively smaller intervals. Begin with two Fibonacci numbers, p (F(n)) and q (F(n+1)), such that p < n ≤ q, where n is the size of the array. The first step checks location p. The size of the next interval is p, if the key is less than the item at that location, or q-p (F(n-1)) if it is greater.
Aggregate child (... is a part of or used in me.)
Fibonacci number, search locations are a Fibonacci tree.
See also linear search, interpolation search, binary search, jump search.
Note: This is similar to a binary search, but only needs subtraction, instead of divide by two or shift right, to compute the next position.
Author: PEB
David E. Ferguson, Fibonaccian Searching, CACM, 3(12):648, December 1960.
Also [Knuth98, 3:417, Sect. 6.2.1].
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 14 May 2007.
HTML page formatted Mon May 14 10:01:56 2007.
Cite this as:
Paul E. Black, "Fibonaccian search", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 14 May 2007. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/fibonaccianSearch.html
