Fibonacci search technique

<h2 id="algorithm">Algorithm</h2>
Let k be defined as an element in F, the array of Fibonacci numbers. n = Fm is the array size. If n 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 = 1.
To test whether an item is in the list of ordered numbers, follow these steps:

<ol><li>Set k = m.</li>
<li>If k = 0, stop. There is no match; the item is not in the array.</li>
<li>Compare the item against element in Fk−1.</li>
<li>If the item matches, stop.</li>
<li>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.</li>
<li>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.</li></ol>
Alternative implementation (from "Sorting and Searching" by Knuth<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>):
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, p, q) ← (i − q, q, p − q) (which moves p and q one position back in the Fibonacci sequence); then return to Step 2
Step 4. [Increase i] If p=1, the algorithm terminates unsuccessfully. Otherwise set (i, p, q) ← (i + q, p − q, 2q − p) (which moves p and q two positions back in the Fibonacci sequence); and return to Step 2
The two variants of the algorithm presented above always divide the current interval into a larger and a smaller subinterval. The original algorithm,<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> however, would divide the new interval into a smaller and a larger subinterval in Step 4. This has the advantage that the new i is closer to the old i and is more suitable for accelerating searching on magnetic tape.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Search_algorithms/eJuw0nyz">Search algorithms</a></li></ul>

<ul><li>Lourakis, Manolis. <a href="http://www.ics.forth.gr/~lourakis/fibsrch/">"Fibonaccian search in C"</a>. Retrieved January 18, 2007. Implements the above algorithm (not Ferguson's original one).</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Ferguson, 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). <a href="https://doi.org/10.1145%2F367487.367496" target="_blank">https://doi.org/10.1145%2F367487.367496</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Overholt, K. J. (1973). "Efficiency of the Fibonacci search method". BIT Numerical Mathematics. 13 (1): 92–96. doi:10.1007/BF01933527. S2CID 120681132. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Ferguson, 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). <a href="https://doi.org/10.1145%2F367487.367496" target="_blank">https://doi.org/10.1145%2F367487.367496</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">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. <a href="https://doi.org/10.1090%2FS0002-9939-1953-0055639-3" target="_blank">https://doi.org/10.1090%2FS0002-9939-1953-0055639-3</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Knuth, Donald E. (2003). The Art of Computer Programming. Vol. 3 (Second ed.). p. 418. <a href="/wiki/The_Art_of_Computer_Programming" target="_blank">/wiki/The_Art_of_Computer_Programming</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Ferguson, 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). <a href="https://doi.org/10.1145%2F367487.367496" target="_blank">https://doi.org/10.1145%2F367487.367496</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
</ol>

Fibonacci search technique open-in-new

Fibonacci search technique