Skip to main content

Fibonacci Search (Geeks for Geeks)

Fibonacci Search is an efficient search algorithm for sorted arrays. It uses Fibonacci numbers to divide the array into smaller subarrays, reducing the search space at each step. This algorithm is particularly useful when the size of the input array is large.

  1. Find the smallest Fibonacci number greater than or equal to the length of the array.
  2. Use the Fibonacci number to divide the array into two parts.
  3. Compare the target element with the element at the division point.
  4. If the target element is equal to the element at the division point, return the index.
  5. If the target element is less than the element at the division point, repeat the process for the left subarray.
  6. If the target element is greater than the element at the division point, repeat the process for the right subarray.

How does Fibonacci Search work?

  • It calculates Fibonacci numbers and uses them to divide the array into smaller subarrays.
  • The search process is repeated within the appropriate subarray based on comparisons.
  • The algorithm reduces the search space at each step, making the search efficient.

Problem Description

Given a sorted list and a target element, implement the Fibonacci Search algorithm to find the index of the target element in the list. If the element is not present, return -1.

Examples

Example 1: Input: list = [10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100] target = 85 Output: 8

Example 2: Input: list = [10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100] target = 55 Output: -1

Your Task:

You don't need to read input or print anything. Complete the function fibonacci_search() which takes arr[], N and K as input parameters and returns the index of K in the array. If K is not present in the array, return -1.

Expected Time Complexity: O(logN)O(\log N) Expected Auxiliary Space: O(1)O(1)

Constraints

  • 1<=N<=1051 <= N <= 10^5
  • 1<=arr[i]<=1061 <= arr[i] <= 10^6
  • 1<=K<=1061 <= K <= 10^6

Implementation

def fibonacci_search(arr, x):
n = len(arr)
fib_mm2 = 0 # (m-2)'th Fibonacci No.
fib_mm1 = 1 # (m-1)'th Fibonacci No.
fib_m = fib_mm1 + fib_mm2 # m'th Fibonacci

while (fib_m < n):
fib_mm2 = fib_mm1
fib_mm1 = fib_m
fib_m = fib_mm2 + fib_mm1

offset = -1

while (fib_m > 1):
i = min(offset + fib_mm2, n - 1)

if (arr[i] < x):
fib_m = fib_mm1
fib_mm1 = fib_mm2
fib_mm2 = fib_m - fib_mm1
offset = i
elif (arr[i] > x):
fib_m = fib_mm2
fib_mm1 = fib_mm1 - fib_mm2
fib_mm2 = fib_m - fib_mm1
else:
return i

if (fib_mm1 and arr[offset + 1] == x):
return offset + 1

return -1

Complexity Analysis

Time Complexity:

O(logN)O(\log N), where NN is the number of elements in the list. The Fibonacci numbers are used to reduce the search space efficiently.

Space Complexity:

O(1)O(1), as no extra space is required apart from the input list.

Advantages and Disadvantages

Advantages:

Efficient for large sorted arrays.

Reduces the search space efficiently using Fibonacci numbers.

Disadvantages:

Requires the list to be sorted.

May not be as intuitive as other search algorithms like binary search.