fibonacci search algorithm c++
Fibonacci Search Algorithm in C++
The Fibonacci search algorithm is an efficient search algorithm based on the Fibonacci sequence. It is used to search for an element in a sorted array. Here are the steps of the Fibonacci search algorithm:
Initialize the Fibonacci Numbers: Initialize two variables,
fibM
andfibMMinus2
, to store the current and previous Fibonacci numbers, respectively. SetfibM
to 0 andfibMMinus2
to 1.Calculate Fibonacci Numbers: Calculate the Fibonacci numbers until
fibM
is greater than or equal to the length of the array. UpdatefibM
andfibMMinus2
using the formulafibM = fibM + fibMMinus2
andfibMMinus2 = fibM - fibMMinus2
.Initialize the Offset and Comparison Index: Initialize two variables,
offset
andi
, to store the offset and the comparison index, respectively. Setoffset
to 0 andi
to the minimum ofoffset + fibMMinus2
and the length of the array minus 1.Search Loop: Perform a loop to compare the search element with the element at index
i
in the array. If the element at indexi
is equal to the search element, returni
. If the element at indexi
is less than the search element, update the variablesoffset
,fibM
,fibMMinus2
, andi
accordingly. If the element at indexi
is greater than the search element, update the variablesfibM
,fibMMinus2
, andi
accordingly.Final Comparison: After the loop, check if
fibMMinus2
is 0 and the element at indexoffset
is equal to the search element. If it is, returnoffset
; otherwise, the element is not present in the array.
This algorithm efficiently narrows down the search range using the Fibonacci numbers and the golden ratio to achieve a time complexity of O(log n) for searching in a sorted array.