Jump to content

Fibonacci search technique

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by David N. Jansen (talk | contribs) at 11:08, 30 June 2017 (throrough rewrite of introduction, mostly based on what I added to the Talk page earlier today). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
This article is about the programming algorithm. For the technique for finding extremum of a mathematical function, see Golden section search.

In computer science, 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.[1] Compared to binary search where the sorted array is divided into two equal-sized parts, one of which is examined further, Fibonacci search divides the array into two parts that have sizes that are consecutive Fibonacci numbers. On average, this leads to about 4% more comparisons to be executed[2], but it has the advantage that one only needs addition and subtraction to calculate the indices of the accessed array elements, while classical binary search needs bit-shift, division or multiplication,[1] operations that were less common at the time Fibonacci search was first published. Fibonacci search has a average- and worst-case complexity of O(log n) (see Big O notation).

If the elements being searched have non-uniform access memory storage (i. e., the time needed to access a storage location varies depending on the location accessed), the Fibonacci search may have the advantage over binary search in slightly reducing the average time needed to access a storage location. If the machine executing the search has a direct mapped CPU cache, binary search may lead to more cache misses because the elements that are accessed often tend to gather in only a few cache lines; this is mitigated by splitting the array in parts that do not tend to be powers of two. If the data is stored on a magnetic tape where seek time depends on the current head position, a tradeoff between longer seek time and more comparisons may lead to a search algorithm that is skewed similarly to Fibonacci search.

Fibonacci search is derived from an algorithm by Jack Kiefer (1953) to search for the maximum or minimum of a unimodal function in an interval.[3]

Algorithm

Let k be defined as an element in F, the array of Fibonacci numbers. n = Fm is the array size. If n 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:

  1. Set k = m.
  2. If k = 0, stop. There is no match; the item is not in the array.
  3. Compare the item against element in Fk−1.
  4. If the item matches, stop.
  5. 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.
  6. 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.

Alternative implementation (from "Sorting and Searching" by Knuth[4]):

Given a table of records R1, R2, ..., RN whose keys are in increasing order K1 < K2 < ... < KN, the algorithm searches for a given argument K. Assume N+1 = Fk+1

Step 1. [Initialize] i ← Fk, p ← Fk-1, q ← Fk-2 (throughout the algorithm, p and q will be consecutive Fibonacci numbers)

Step 2. [Compare] If K < Ki, go to Step 3; if K > Ki go to Step 4; and if K = Ki, the algorithm terminates successfully.

Step 3. [Decrease i] If q=0, the algorithm terminates unsuccessfully. Otherwise set (i, p, q) ← (p, q, p - q) (which moves p and q one position back in the Fibonacci sequence); then return to Step 2

Step 4. [Increase i] If p=1, the algorithm terminates unsuccessfully. Otherwise set (i,p,q) ← (i + q, p - q, 2q - p) (which moves p and q two positions back in the Fibonacci sequence); and return to Step 2

The two variants of the algorithm presented above always divide the current interval into a larger and a smaller subinterval. The original algorithm[1], however, would divide the new interval into a smaller and a larger subinterval in Step 4. This has the advantage that the new i is closer to the old i and is more suitable for accelerating searching on magnetic tape.

See also

References

  1. ^ a b c David E. Ferguson. Fibonaccian searching. Communications of the ACM 3(12)1960:648. Note that the running time analysis is this article is flawed, as pointed out by Overholt (1972).
  2. ^ K. J. Overholt: Efficiency of the Fibonacci search method. BIT Numerical Mathematics 13(1)1973:92–96
  3. ^ J. Kiefer. Sequential minimax search for a maximum. Proc. American Mathematical Society 4, 1953:502–506
  4. ^ Donald E. Knuth, "The Art of Computer Programming (second edition)", vol. 3, p. 418, Nov. 2003.
  • Manolis Lourakis, "Fibonaccian search in C". [1]. Retrieved January 18, 2007. Implements the above algorithm (not Ferguson's original one).
Retrieved from "https://en.wikipedia.org/w/index.php?title=Fibonacci_search_technique&oldid=788251622"