Fibonacci search technique
- Fibonacci search technique
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 has the property of examininglocations whose addresses have lower dispersion. Therefore, when the elements being searched havenon-uniform access memory storage (i.e., the time needed to access a storage locationvaries depending on the location previously accessed), the Fibonacci search has anadvantage over binary search in slightly reducing the average time needed to accessa storage location. The typical example of non-uniform access storage is that ofa magnetic tape, where the time to access a particular element is proportional toits distance from the element currently under the tape's head. Note, however, that large arraysnot 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" = "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, "F"1 = 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 "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.
See also
* Golden section search
References
* David E. Ferguson, "Fibonaccian searching", "Communications of the ACM", vol. 3 , is. 12, p. 648, Dec. 1960.
* Manolis Lourakis, "Fibonaccian search in C". [http://www.ics.forth.gr/~lourakis/fibsrch/] . Retrieved January 18, 2007. Implements Ferguson's algorithm.
Wikimedia Foundation.
2010.
Look at other dictionaries:
Fibonacci number — A tiling with squares whose sides are successive Fibonacci numbers in length … Wikipedia
Fibonacci — Infobox Scientist box width = 300px name = Leonardo of Pisa (Fibonacci) image width = 150px caption = Leonardo of Pisa, Fibonacci birth date = c. 1170 birth place = Pisa, Italy death date = c. 1250 death place = Pisa, Italy residence = Italy… … Wikipedia
Golden section search — The golden section search is a technique for finding the extremum (minimum or maximum) of a unimodal function by successively narrowing the range of values inside which the extremum is known to exist. The technique derives its name from the fact… … Wikipedia
The Search (TV series) — The Search was a seven part television show on Channel 4, which first aired in on January 7, 2007, the final episode was broadcast on February 24, 2007. The premise of the programme was that ten contestants with unique skills must solve a variety … Wikipedia
cryptology — cryptologist, n. cryptologic /krip tl oj ik/, cryptological, adj. /krip tol euh jee/, n. 1. cryptography. 2. the science and study of cryptanalysis and cryptography. [1635 45; < NL cryptologia. See CRYPTO , LOGY] * * * Introduction … Universalium
Dynamic programming — For the programming paradigm, see Dynamic programming language. In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems… … Wikipedia
Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… … Wikipédia en Français
List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… … Wikipedia
Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants … Wikipédia en Français
Egyptian fraction — An Egyptian fraction is the sum of distinct unit fractions, such as frac{1}{2}+ frac{1}{3}+ frac{1}{16}. That is, each fraction in the expression has a numerator equal to 1 and a denominator that is a positive integer, and all the denominators… … Wikipedia
