Fibonacci Search Technique - Algorithm

Algorithm

Let k be defined as an element in F, the array of Fibonacci numbers. n = F_m is the array size. If the array size 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 ≥ 0, F₁ = 1, and F₀ = 0.

To test whether an item is in the list of ordered numbers, follow these steps:

1. Set k = m.
2. If k = 0, stop. There is no match; the item is not in the array.
3. Compare the item against element in F_k−1.
4. If the item matches, stop.
5. 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.
6. 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):

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. i ← F_k, p ← F_k-1, q ← F_k-2 (throughout the algorithm, p and q will be consecutive Fibonacci numbers)

Step 2. 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. If q=0, the algorithm terminates unsuccessfully. Otherwise set i ← i - q, and set (p, q) ← (q, p - q); then return to Step 2

Step 4. If p=1, the algorithm terminates unsuccessfully. Otherwise set i ← i + p, p ← p + q, then q ←p - q; and return to Step 2