Fibonacci search technique: Difference between revisions

Content deleted Content added

Inline

Revision as of 03:19, 27 March 2010

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. Compared to binary search, Fibonacci search examines locations whose addresses have lower dispersion. Therefore, when 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 previously accessed), the Fibonacci search has an advantage over binary search in slightly reducing the average time needed to access a storage location. The typical example of non-uniform access storage is that of a magnetic tape, where the time to access a particular element is proportional to its distance from the element currently under the tape's head. Note, however, that large arrays not fitting in cache or even in RAM can also be considered as non-uniform access examples. Fibonacci search has a complexity of O(log(x)) (see Big O notation).

Algorithm

Let k be defined as an element in F, the array of Fibonacci numbers. n = F_m is the array size. If the array size is not a Fibonacci number, let F_m be the smallest number in F that is greater than n.

The array of Fibonacci numbers is defined where F_k+2 = F_k+1 + F_k, when k ≥ 0, F₁ = 1, and F₀ = 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 F_k−1.
If the item matches, stop.
If the item is less than entry F_k−1, discard the elements from positions F_k−1 + 1 to n. Set k = k − 1 and return to step 2.
If the item is greater than entry F_k−1, discard the elements from positions 1 to F_k−1. Renumber the remaining elements from 1 to F_k−2, set k = k − 2, and return to step 2.

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.

@@ Line 2: / Line 2: @@
 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 number]]s.
 Compared to [[binary search algorithm|binary search]], Fibonacci search examines
-locations whose addresses have lower dispersion. Therefore, when the elements being searched have
+locations whose addresses have lower dispersion. Therefore, when the elements being searched have non-uniform access memory storage (i.e., the time needed to access a storage location
-non-uniform access memory storage (i.e., the time needed to access a storage location
 varies depending on the location previously accessed), the Fibonacci search has an
 advantage over binary search in slightly reducing the average time needed to access
@@ Line 21: / Line 20: @@
 #Set ''k'' = ''m''.
 #If ''k'' = 0, stop. There is no match; the item is not in the array.
-#Compare the item against element in ''F''<sub>''k''-1</sub>.
+#Compare the item against element in ''F''<sub>''k''&minus;1</sub>.
 #If the item matches, stop.
-#If the item is less than entry ''F''<sub>''k''-1</sub>, discard the elements from positions ''F''<sub>''k''-1</sub> + 1 to ''n''. Set ''k'' = ''k'' - 1 and return to step 2.
+#If the item is less than entry ''F''<sub>''k''&minus;1</sub>, discard the elements from positions ''F''<sub>''k''&minus;1</sub>&nbsp;+&nbsp;1 to ''n''. Set ''k''&nbsp;=&nbsp;''k''&nbsp;&minus;&nbsp;1 and return to step 2.
-#If the item is greater than entry ''F''<sub>''k''-1</sub>, discard the elements from positions 1 to ''F''<sub>''k''-1</sub>. Renumber the remaining elements from 1 to ''F''<sub>''k''-2</sub>, set ''k'' = ''k'' - 2, and return to step 2.
+#If the item is greater than entry ''F''<sub>''k''&minus;1</sub>, discard the elements from positions 1 to ''F''<sub>''k''&minus;1</sub>. Renumber the remaining elements from 1 to ''F''<sub>''k''&minus;2</sub>, set ''k''&nbsp;=&nbsp;''k''&nbsp;&minus;&nbsp;2, and return to step&nbsp;2.
 == See also ==