Fibonacci search technique
Encyclopedia
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 number
s.
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
).
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:
Alternative implementation (from "Sorting and Searching" by Knuth):
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 ← i - q, and set (p, q) ← (q, p - q); then return to Step 2
Step 4. [Increase i] If p=1, the algorithm terminates unsuccessfully. Otherwise set i ← i + q, p ← p - q, then q ←q - p; and return to Step 2
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, the Fibonacci search technique is a method of searching a sorted array
Sorted array
A sorted array is an array data structure in which each element is sorted in numerical, alphabetical, or some other order, and placed at equally spaced addresses in computer memory. It is typically used in computer science to implement static lookup tables to hold multiple values which has the same...
using a divide and conquer algorithm
Divide and conquer algorithm
In computer science, divide and conquer is an important algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same type, until these become simple enough to be solved directly...
that narrows down possible locations with the aid of Fibonacci number
Fibonacci number
In mathematics, the Fibonacci numbers are the numbers in the following integer sequence:0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots\; ....
s.
Compared to binary search
Binary search algorithm
In computer science, a binary search or half-interval search algorithm finds the position of a specified value within a sorted array. At each stage, the algorithm compares the input key value with the key value of the middle element of the array. If the keys match, then a matching element has been...
, 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
Magnetic tape
Magnetic tape is a medium for magnetic recording, made of a thin magnetizable coating on a long, narrow strip of plastic. It was developed in Germany, based on magnetic wire recording. Devices that record and play back audio and video using magnetic tape are tape recorders and video tape recorders...
, 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
Cache
In computer engineering, a cache is a component that transparently stores data so that future requests for that data can be served faster. The data that is stored within a cache might be values that have been computed earlier or duplicates of original values that are stored elsewhere...
or even in RAM
Ram
-Animals:*Ram, an uncastrated male sheep*Ram cichlid, a species of freshwater fish endemic to Colombia and Venezuela-Military:*Battering ram*Ramming, a military tactic in which one vehicle runs into another...
can also be considered as non-uniform access examples.
Fibonacci search has a complexity of O(log(x)) (see Big O notation
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
).
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.
Alternative implementation (from "Sorting and Searching" by Knuth):
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 ← i - q, and set (p, q) ← (q, p - q); then return to Step 2
Step 4. [Increase i] If p=1, the algorithm terminates unsuccessfully. Otherwise set i ← i + q, p ← p - q, then q ←q - p; and return to Step 2