Fibonacci search technique: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 14:37, 24 November 2024

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]

Algorithm

Let k be defined as an element in F, the array of Fibonacci numbers. n = F_m is the array size. If n is not a Fibonacci number, let F_m be the smallest number in F that is greater than n.

The array of Fibonacci numbers is defined where $F k +2 = F k +1 + F k$ , when $k \geq 0$ , $F 1 = 1$ , and $F 0 = 1$ .

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.

Alternative implementation (from "Sorting and Searching" by Knuth^[4]):

Given a table of records R₁, R₂, ..., R_N whose keys are in increasing order K₁ < K₂ < ... < K_N, the algorithm searches for a given argument K. Assume N+1= F_k+1

Step 1. [Initialize] i ← F_k, p ← F_k−1, q ← F_k−2 (throughout the algorithm, p and q will be consecutive Fibonacci numbers)

Step 2. [Compare] If K < K_i, go to Step 3; if K > K_i go to Step 4; and if K = K_i, 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,^[1] 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.

References

^ ^a ^b ^c 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).
^ 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.
^ Knuth, Donald E. (2003). The Art of Computer Programming. Vol. 3 (Second ed.). p. 418.

Lourakis, Manolis. "Fibonaccian search in C". Retrieved January 18, 2007. Implements the above algorithm (not Ferguson's original one).

[Ferguson1960-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).

[Overholt-2] Overholt, K. J. (1973). "Efficiency of the Fibonacci search method". BIT Numerical Mathematics. 13 (1): 92–96. doi:10.1007/BF01933527. S2CID 120681132.

[3] 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.

[4] Knuth, Donald E. (2003). The Art of Computer Programming. Vol. 3 (Second ed.). p. 418.

[1]

[2]

[3]

[4]

@@ Line 1: / Line 1: @@
+{{Short description|Method of searching a sorted array}}
 {{About|the programming algorithm|the technique for finding extremum of a mathematical function|Golden section search}}
 {{Technical|date=July 2013}}
-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.<ref name="Ferguson1960">[https://doi.org/10.1145/367487.367496 David E. Ferguson. '''Fibonaccian searching.''' ''Communications of the ACM'' 3(12)1960:648]. Note that the running time analysis is this article is flawed, as pointed out by Overholt (1972).</ref> Compared to [[binary search algorithm|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,<ref name="Overholt">[https://doi.org/10.1007/BF01933527 K. J. Overholt: '''Efficiency of the Fibonacci search method.''' ''BIT Numerical Mathematics'' 13(1)1973:92–96]</ref> 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, division or multiplication,<ref name="Ferguson1960" /> 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]]).
+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.<ref name="Ferguson1960">{{cite journal |doi=10.1145/367487.367496 |first=David E. |last=Ferguson |title=Fibonaccian searching |journal=Communications of the ACM |volume=3 |issue=12 |year=1960 |page=648 |s2cid=7982182 |doi-access=free }} Note that the running time analysis is this article is flawed, as pointed out by Overholt in 1972 (published 1973).</ref> Compared to [[binary search algorithm|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,<ref name="Overholt">{{cite journal |doi=10.1007/BF01933527 |first=K. J. |last=Overholt |title=Efficiency of the Fibonacci search method |journal=BIT Numerical Mathematics |volume=13 |issue=1 |year=1973 |pages=92–96 |s2cid=120681132 }}</ref> 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,<ref name="Ferguson1960" /> 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 data storage|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 (statistician)|Jack Kiefer]] (1953) to search for the maximum or minimum of a [[unimodal function]] in an interval.<ref>[http://www.ams.org/journals/proc/1953-004-03/S0002-9939-1953-0055639-3 J. Kiefer. '''Sequential minimax search for a maximum.''' ''Proc. American Mathematical Society'' 4, 1953:502–506]</ref>
+Fibonacci search is derived from [[Golden section search]], an algorithm by [[Jack Kiefer (statistician)|Jack Kiefer]] (1953) to search for the maximum or minimum of a [[unimodal function]] in an interval.<ref>{{cite journal |doi=10.1090/S0002-9939-1953-0055639-3 |first=J. |last=Kiefer |title=Sequential minimax search for a maximum |journal=Proceedings of the American Mathematical Society |volume=4 |year=1953 |issue=3 |pages=502–506 |doi-access=free }}</ref>
 ==Algorithm==
 Let ''k'' be defined as an element in ''F'', the array of Fibonacci numbers. ''n'' = ''F<sub>m</sub>'' is the array size. If ''n'' is not a Fibonacci number, let ''F<sub>m</sub>'' be the smallest number in ''F'' that is greater than ''n''.
-The array of Fibonacci numbers is defined where ''F''<sub>''k''+2</sub> = ''F''<sub>''k''+1</sub>&nbsp;+&nbsp;''F<sub>k</sub>'', when ''k''&nbsp;≥&nbsp;0, ''F''<sub>1</sub> =&nbsp;1, and ''F<sub>0</sub>'' =&nbsp;0.
+The array of Fibonacci numbers is defined where {{math|1=''F''<sub>''k''+2</sub> = ''F''<sub>''k''+1</sub> + ''F<sub>k</sub>''}}, when {{math|1=''k'' ≥ 0}}, {{math|1=''F''<sub>1</sub> = 1}}, and {{math|1=''F<sub>0</sub>'' = 1}}.
 To test whether an item is in the list of ordered numbers, follow these steps:
@@ Line 19: / Line 22: @@
 #Compare the item against element in ''F''<sub>''k''−1</sub>.
 #If the item matches, stop.
-#If the item is less than entry ''F''<sub>''k''−1</sub>, discard the elements from positions ''F''<sub>''k''−1</sub>&nbsp;+&nbsp;1 to ''n''. Set ''k''&nbsp;=&nbsp;''k''&nbsp;−&nbsp;1 and return to step 2.
+#If the item is less than entry ''F''<sub>''k''−1</sub>, discard the elements from positions {{math|1=''F''<sub>''k''−1</sub> + 1}} to ''n''. Set {{math|1=''k'' = ''k'' − 1}} and return to step 2.
-#If the item is greater than entry ''F''<sub>''k''−1</sub>, discard the elements from positions 1 to ''F''<sub>''k''−1</sub>. Renumber the remaining elements from 1 to ''F''<sub>''k''−2</sub>, set ''k''&nbsp;=&nbsp;''k''&nbsp;−&nbsp;2, and return to step&nbsp;2.
+#If the item is greater than entry ''F''<sub>''k''−1</sub>, discard the elements from positions 1 to ''F''<sub>''k''−1</sub>. Renumber the remaining elements from 1 to ''F''<sub>''k''−2</sub>, set {{math|1=''k'' = ''k'' − 2}}, and return to step 2.
-Alternative implementation (from "Sorting and Searching" by Knuth<ref>Donald E. Knuth, "[[The Art of Computer Programming]] (second edition)", vol.&nbsp;3, p.&nbsp;418, Nov. 2003.</ref>):
+Alternative implementation (from "Sorting and Searching" by Knuth<ref>{{cite book |first=Donald E. |last=Knuth |title=[[The Art of Computer Programming]] |edition=Second |volume=3 |page=418 |date=2003 }}</ref>):
-Given a table of records ''R<sub>1</sub>'', ''R<sub>2</sub>'', ..., ''R<sub>N</sub>'' whose keys are in increasing order ''K<sub>1</sub>'' < ''K<sub>2</sub>'' < ... < ''K<sub>N</sub>'', the algorithm searches for a given argument ''K''. Assume ''N+1'' = ''F''<sub>''k''+1</sub>
+Given a table of records ''R<sub>1</sub>'', ''R<sub>2</sub>'', ..., ''R<sub>N</sub>'' whose keys are in increasing order ''K''<sub>1</sub> < ''K''<sub>2</sub> < ... < ''K<sub>N</sub>'', the algorithm searches for a given argument ''K''. Assume ''N''+1= ''F''<sub>''k''+1</sub>
-'''Step 1.''' [Initialize] ''i'' ← ''F''<sub>''k''</sub>, ''p'' ← ''F''<sub>''k''-1</sub>, ''q'' ← ''F''<sub>''k''-2</sub> (throughout the algorithm, ''p'' and ''q'' will be consecutive Fibonacci numbers)
+'''Step 1.''' [Initialize] ''i'' ← ''F''<sub>''k''</sub>, ''p'' ← ''F''<sub>''k''&minus;1</sub>, ''q'' ← ''F''<sub>''k''&minus;2</sub> (throughout the algorithm, ''p'' and ''q'' will be consecutive Fibonacci numbers)
 '''Step 2.''' [Compare] If ''K'' < ''K<sub>i</sub>'', go to ''Step 3''; if ''K'' > ''K<sub>i</sub>'' go to ''Step 4''; and if ''K'' = ''K<sub>i</sub>'', the algorithm terminates successfully.
-'''Step 3.''' [Decrease ''i''] If ''q''=0, the algorithm terminates unsuccessfully. Otherwise set (''i'', ''p'', ''q'') ← (''p'', ''q'', ''p - q'') (which moves ''p'' and ''q'' one position back in the Fibonacci sequence); then return to ''Step 2''
+'''Step 3.''' [Decrease ''i''] If ''q''=0, the algorithm terminates unsuccessfully. Otherwise set (''i'', ''p'', ''q'') ← (''i'' &minus; ''q'', ''q'', ''p'' &minus; ''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''
+'''Step 4.''' [Increase ''i''] If ''p''=1, the algorithm terminates unsuccessfully. Otherwise set (''i'', ''p'', ''q'') ← (''i'' + ''q'', ''p'' &minus; ''q'', 2''q'' &minus; ''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,<ref name="Ferguson1960" /> 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.
@@ Line 41: / Line 44: @@
 ==References==
 <references />
-* Manolis Lourakis, "Fibonaccian search in C". [http://www.ics.forth.gr/~lourakis/fibsrch/]. Retrieved January 18, 2007. Implements the above algorithm (not Ferguson's original one).
+*{{cite web |first=Manolis |last=Lourakis |title=Fibonaccian search in C |url=http://www.ics.forth.gr/~lourakis/fibsrch/ |accessdate=January 18, 2007 }} Implements the above algorithm (not Ferguson's original one).
 {{DEFAULTSORT:Fibonacci Search Technique}}

Latest revision as of 14:37, 24 November 2024

Algorithm

See also

References