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. 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 CPU 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).
Fibonacci search was first devised by Kiefer (1953) as a minimax search for the maximum (minimum) of a unimodal function in an interval.
Read more about Fibonacci Search Technique: Algorithm
Famous quotes containing the words search and/or technique:
“If ever the search for a tranquil belief should end,
The future might stop emerging out of the past,
Out of what is full of us; yet the search
And the future emerging out of us seem to be one.”
—Wallace Stevens (1879–1955)
“Every notable advance in technique or organization has to be paid for, and in most cases the debit is more or less equivalent to the credit. Except of course when it’s more than equivalent, as it has been with universal education, for example, or wireless, or these damned aeroplanes. In which case, of course, your progress is a step backwards and downwards.”
—Aldous Huxley (1894–1963)