Fibonacci search technique
From Wikipedia, the free encyclopedia
This article is about the programming algorithm. For the technique for finding extremum of a mathematical function, see golden section search.
The Fibonacci search technique is a method of searching a sorted array using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers. This method is faster than traditional binary search algorithms, with a complexity of O(log(x)) (see Big O notation).
[edit] Algorithm
Let k be defined as an element in F, the array of Fibonacci numbers. n = Fm is the array size. If the array size is not a Fibonacci number, let Fm be the smallest number in F that is greater than n.
The array of Fibonacci numbers is defined where Fk+2 = Fk+1 + Fk, when k ≥ 0, F1 = 1, and F0 = 0.
To test whether an item is in the list of ordered numbers, follow these steps:
- Set k = m.
- If k = 0, stop. There is no match; the item is not in the array.
- Compare the item against element in Fk-1.
- If the item matches, stop.
- If the item is less than entry Fk-1, discard the elements from positions Fk-1 + 1 to n. Set k = k - 1 and return to step 2.
- If the item is greater than entry Fk-1, discard the elements from positions 1 to Fk-1. Renumber the remaining elements from 1 to Fk-2, set k = k - 2, and return to step 2.
[edit] References
- David E. Ferguson, "Fibonaccian searching", Communications of the ACM, vol. 3 , is. 12, p. 648, Dec. 1960.
- Manolis Lourakis, "Fibonaccian search in C". [1]. Retrieved January 18, 2007. Implements Ferguson's algorithm.
