Searching Algorithms Questions Medium
The Fibonacci search algorithm is a searching technique that is based on the Fibonacci sequence. It is an efficient search algorithm that works on sorted arrays.
The algorithm starts by defining two Fibonacci numbers, Fm and Fm+1, such that Fm+1 is the smallest Fibonacci number greater than or equal to the length of the array. Initially, m is set to 0.
The algorithm then compares the key element with the element at index Fm. If the key is equal to the element at Fm, the search is successful, and the algorithm returns the index of the element.
If the key is less than the element at Fm, the algorithm updates the values of Fm and Fm+1 by considering the Fibonacci numbers before Fm. Specifically, it sets Fm to Fm+1 - Fm-1 and Fm+1 to Fm - Fm-1. The value of m is also updated to m-1.
If the key is greater than the element at Fm, the algorithm updates the values of Fm and Fm+1 by considering the Fibonacci numbers after Fm. Specifically, it sets Fm to Fm+1 and Fm+1 to Fm - Fm-1. The value of m is also updated to m-2.
The algorithm repeats these steps until it either finds the key element or determines that the key is not present in the array. If the search is unsuccessful and the value of m becomes 1 or 0, the algorithm concludes that the key is not present in the array.
The Fibonacci search algorithm has a time complexity of O(log n), making it efficient for searching in large arrays. However, it requires the array to be sorted, and the Fibonacci numbers need to be precomputed or generated dynamically during the search process.