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:

  1. Initialize the Fibonacci Numbers: Initialize two variables, fibM and fibMMinus2, to store the current and previous Fibonacci numbers, respectively. Set fibM to 0 and fibMMinus2 to 1.

  2. Calculate Fibonacci Numbers: Calculate the Fibonacci numbers until fibM is greater than or equal to the length of the array. Update fibM and fibMMinus2 using the formula fibM = fibM + fibMMinus2 and fibMMinus2 = fibM - fibMMinus2.

  3. Initialize the Offset and Comparison Index: Initialize two variables, offset and i, to store the offset and the comparison index, respectively. Set offset to 0 and i to the minimum of offset + fibMMinus2 and the length of the array minus 1.

  4. Search Loop: Perform a loop to compare the search element with the element at index i in the array. If the element at index i is equal to the search element, return i. If the element at index i is less than the search element, update the variables offset, fibM, fibMMinus2, and i accordingly. If the element at index i is greater than the search element, update the variables fibM, fibMMinus2, and i accordingly.

  5. Final Comparison: After the loop, check if fibMMinus2 is 0 and the element at index offset is equal to the search element. If it is, return offset; 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.