Explain what is Fibonacci Search technique?

Fibonacci Search is a search algorithm that finds the position of a target value in a sorted array using the Fibonacci sequence. It is an efficient searching technique that has a time complexity of O(log n).

Here’s how the Fibonacci Search algorithm works:

  1. Determine the Fibonacci numbers:
    • Start by generating a sequence of Fibonacci numbers that includes numbers greater than or equal to the size of the array to be searched.
    • The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones: 0, 1, 1, 2, 3, 5, 8, 13, 21, …
  2. Initialize variables:
    • Let n be the size of the array.
    • Initialize two pointers: left pointing to the start of the array (index 0) and right pointing to the end of the array (index n-1).
    • Initialize an index variable mid as the minimum of left + Fibonacci[k-2] and n-1 (where k is the smallest Fibonacci number greater than or equal to n).
  3. Search Process:
    • Compare the target value with the element at index mid.
    • If the target value is equal to the element at mid, the search is successful, and mid is the position of the target value.
    • If the target value is less than the element at mid, update right to mid - 1 and recalculate mid using the Fibonacci sequence (moving left in the array).
    • If the target value is greater than the element at mid, update left to mid + 1 and recalculate mid using the Fibonacci sequence (moving right in the array).
    • Repeat the comparison until the target value is found or left becomes greater than right.
  4. Termination:
    • The search terminates when the target value is found or left becomes greater than right, indicating that the target value is not present in the array.

Fibonacci Search works by dividing the search space into smaller subarrays using Fibonacci numbers. It narrows down the search range by moving left or right based on the comparison with the target value. The use of Fibonacci numbers ensures efficient movement and a balanced search space.

Fibonacci Search is particularly useful when the array size is large and unevenly distributed. It performs well in scenarios where random access to elements is costly (e.g., when accessing elements from external storage).

However, it’s worth noting that Fibonacci Search is not commonly used in practice compared to other search algorithms such as binary search. This is because binary search has a similar time complexity of O(log n) but performs fewer comparisons and has better cache locality.

error: Content is protected !!