This article is about the programming algorithm. For the technique for finding extremum of a mathematical function, see Golden section search.
This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details.(July 2013) (Learn how and when to remove this message)
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 (see Bitwise operation), division or multiplication,[1] operations that were less common at the time Fibonacci search was first published. Fibonacci search has an average- and worst-case complexity of O(log n) (see Big O notation).
The Fibonacci sequence has the property that a number is the sum of its two predecessors. Therefore the sequence can be computed by repeated addition. The ratio of two consecutive numbers approaches the Golden ratio, 1.618... Binary search works by dividing the seek area in equal parts (1:1). Fibonacci search can divide it into parts approaching 1:1.618 while using the simpler operations.
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 Golden section search, an algorithm by Jack Kiefer (1953) to search for the maximum or minimum of a unimodal function in an interval.[3]
^ abFerguson, David E. (1960). "Fibonaccian searching". Communications of the ACM. 3 (12): 648. doi:10.1145/367487.367496. S2CID 7982182. Note that the running time analysis is this article is flawed, as pointed out by Overholt in 1972 (published 1973).
^Overholt, K. J. (1973). "Efficiency of the Fibonacci search method". BIT Numerical Mathematics. 13 (1): 92–96. doi:10.1007/BF01933527. S2CID 120681132.
^Kiefer, J. (1953). "Sequential minimax search for a maximum". Proceedings of the American Mathematical Society. 4 (3): 502–506. doi:10.1090/S0002-9939-1953-0055639-3.
and 23 Related for: Fibonacci search technique information
In computer science, the Fibonaccisearchtechnique is a method of searching a sorted array using a divide and conquer algorithm that narrows down possible...
after Fibonacci because of a connection to the Fibonacci numbers. Examples include the Brahmagupta–Fibonacci identity, the Fibonaccisearchtechnique, and...
vice versa Sorted lists Binary search algorithm: locates an item in a sorted sequence Fibonaccisearchtechnique: search a sorted sequence using a divide...
In computer science, a Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-ordered trees. It has a better...
Lucas pseudoprimes and Fibonacci pseudoprimes are composite integers that pass certain tests which all primes and very few composite numbers pass: in...
pairing heaps or Fibonacci heaps can provide better bounds for some operations. Alternatively, when a self-balancing binary search tree is used, insertion...
strict Fibonacci heap is a priority queue data structure with low worst case time bounds. It matches the amortized time bounds of the Fibonacci heap in...
unsigned hash(unsigned K) { K ^= K >> (w-m); return (a*K) >> (w-m); } Fibonacci hashing is a form of multiplicative hashing in which the multiplier is...
all three being mathematicians of Moroccan origin. Leonardo of Pisa (Fibonacci) devoted Chapter 13 of his book Liber Abaci (AD 1202) to explaining and...
1137/100785351. Fredman, Michael Lawrence; Tarjan, Robert E. (July 1987). "Fibonacci heaps and their uses in improved network optimization algorithms" (PDF)...
parent (base case), or One's parent's ancestor (recursive step). The Fibonacci sequence is another classic example of recursion: Fib(0) = 0 as base case...
sub-problems. For example, consider the recursive formulation for generating the Fibonacci sequence: Fi = Fi−1 + Fi−2, with base case F1 = F2 = 1. Then F43 = F42 + F41...
partitioning Full binary tree B*-tree Heap Binary heap Binomial heap Fibonacci heap 2-3 heap Kd-tree Cover tree Decision tree Empty tree Evolutionary...
(i.e., search and replace). Sequence patterns (e.g., a text string) are often described using regular expressions and matched using techniques such as...
Corporation. P-923. Fredman, Michael Lawrence; Tarjan, Robert E. (1984). Fibonacci heaps and their uses in improved network optimization algorithms. 25th...
periods such as the Mersenne twister, generalized shift register and Lagged Fibonacci generators. Mersenne primes Mp are closely connected to perfect numbers...
1137/100785351. Fredman, Michael Lawrence; Tarjan, Robert E. (July 1987). "Fibonacci heaps and their uses in improved network optimization algorithms" (PDF)...
this strategy. Another strategy is the Fibonacci system, where bets are calculated according to the Fibonacci sequence. Regardless of the specific progression...
1137/100785351. Fredman, Michael Lawrence; Tarjan, Robert E. (July 1987). "Fibonacci heaps and their uses in improved network optimization algorithms" (PDF)...
this article but any other base (as well as other possibilities such as Fibonacci numbers) can also be utilized. If using the binary system, a set of n...
Electronic Journal of Combinatorics European Journal of Combinatorics The Fibonacci Quarterly Finite Fields and Their Applications Geombinatorics Graphs and...
Global Information