Begin Fibonacci Search
n <- size of the input array
offset = -1
Fm2 := 0
Fm1 := 1
Fm := Fm2 + Fm1
while Fm < n
do: Fm2 = Fm1
Fm1 = Fm
Fm = Fm2 + Fm1
done while fm > 1
do: i := minimum of (offset + fm2, n – 1)
if (A[i] < x)
then: Fm := Fm1
Fm1 := Fm2
Fm2 := Fm - Fm1
offset = i
end
else if (A[i] > x)
then: Fm = Fm2
Fm1 = Fm1 - Fm2
Fm2 = Fm - Fm1
end
else
return i;
end
Done
if (Fm1 and Array[offset + 1] == x)
then: return offset + 1
end
return invalid location;
End
The Fibonacci Search algorithm takes logarithmic time complexity to search for an
element. Since it is based on a divide on a conquer approach and is similar to idea of
binary search, the time taken by this algorithm to be executed under the worst case
consequences is O(log n).
Example
Suppose we have a sorted array of elements {12, 14, 16, 17, 20, 24, 31, 43, 50, 62}
and need to identify the location of element 24 in it using Fibonacci Search.
Step 1
The size of the input array is 10. The smallest Fibonacci number greater than 10 is 13.
Therefore, Fm = 13, Fm-1 = 8, Fm-2 = 5.
We initialize offset = -1
Step 2
In the first iteration, compare it with the element at index = minimum (offset + F m-2, n
– 1) = minimum (-1 + 5, 9) = minimum (4, 9) = 4.
The fourth element in the array is 20, which is not a match and is less than the key
element.
Step 3
In the second iteration, update the offset value and the Fibonacci numbers.
Since the key is greater, the offset value will become the index of the element, i.e. 4.
Fibonacci numbers are updated as Fm = Fm-1 = 8.
Fm-1 = 5, Fm-2 = 3.
Now, compare it with the element at index = minimum (offset + Fm-2, n – 1) =
minimum (4 + 3, 9) = minimum (7, 9) = 7.
Element at the 7th index of the array is 43, which is not a match and is also lesser than
the key.
Step 4
We discard the elements after the 7th index, so n = 7 and offset value remains 4.
Fibonacci numbers are pushed two steps backward, i.e. Fm = Fm-2 = 3.
Fm-1 = 2, Fm-2 = 1.
Now, compare it with the element at index = minimum (offset + Fm-2, n – 1) =
minimum (4 + 1, 6) = minimum (5, 7) = 5.
The element at index 5 in the array is 24, which is our key element. 5th index is
returned as the output for this example array.
