The Fibonacci Search Algorithm is a fascinating comparison-based searching method that uses the properties of the Fibonacci sequence and the golden ratio to locate an element within a sorted array. Unlike binary search, which splits intervals by half, Fibonacci Search uses Fibonacci numbers to divide the search range more cleverly. This often results in fewer comparisons and can be particularly efficient on large datasets where random access is costly.
What Is Fibonacci Search?
Fibonacci Search is a technique derived from the Fibonacci sequence, where each term is the sum of the two preceding ones. The search algorithm uses these numbers to progressively narrow down the possible location of the target element by slicing the array into segments defined by Fibonacci numbers.
In simpler terms, instead of splitting an array into two equal halves, Fibonacci search partitions it based on a ratio connected to the golden ratio (~1.618), which leads to efficient searching steps without recalculating midpoints often.
Why Fibonacci Search?
- It minimizes the number of costly division or multiplication operations.
- It works exceptionally well when data is stored in sequential storage (like tapes or linked memory).
- It ensures search complexity is
O(log n)like binary search, but with fewer index calculations. - It adapts naturally to the golden ratio, which makes subdivisions closely optimal.
Step-by-Step Working of Fibonacci Search
Let’s walk through the process:
- Find the smallest Fibonacci number greater than or equal to the size of the array (
n). - Use this Fibonacci number to determine the interval for comparison.
- Compare the element at the offset index with the target value.
- Based on the comparison, eliminate a range of elements and move the Fibonacci markers down the sequence.
- Repeat until the element is found or the range reduces to zero.
Python Implementation of Fibonacci Search
Here’s a Python-friendly implementation you can copy and run:
def fibonacci_search(arr, x):
n = len(arr)
# Initialize fibonacci numbers
fibMMm2 = 0 # (m-2)'th Fibonacci
fibMMm1 = 1 # (m-1)'th Fibonacci
fibM = fibMMm2 + fibMMm1 # m'th Fibonacci
# Find the smallest Fibonacci number ≥ n
while fibM < n:
fibMMm2 = fibMMm1
fibMMm1 = fibM
fibM = fibMMm2 + fibMMm1
offset = -1
while fibM > 1:
i = min(offset + fibMMm2, n-1)
if arr[i] < x:
fibM = fibMMm1
fibMMm1 = fibMMm2
fibMMm2 = fibM - fibMMm1
offset = i
elif arr[i] > x:
fibM = fibMMm2
fibMMm1 = fibMMm1 - fibMMm2
fibMMm2 = fibM - fibMMm1
else:
return i
if fibMMm1 and offset+1 < n and arr[offset+1] == x:
return offset+1
return -1
# Example usage
arr = [10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100]
x = 85
result = fibonacci_search(arr, x)
print("Element found at index:", result)
Output:
Element found at index: 8
Visual Representation of Search
The following diagram shows how Fibonacci search narrows down the array search space:
Complexity Analysis
- Time Complexity:
O(log n)comparisons, similar to Binary Search. - Space Complexity:
O(1)since only a few variables are maintained. - More efficient in large sorted arrays on sequential memory than binary search, as it reduces jumps.
Advantages of Fibonacci Search
- No division operations, only subtraction and addition.
- Good for systems where division operation is expensive.
- Retains ordered partitioning of array like Binary Search.
Limitations of Fibonacci Search
- Only efficient for sorted arrays.
- Not commonly used in practice when random access is cheap.
- Slightly more complex to implement than binary search.
Conclusion
The Fibonacci Search Algorithm elegantly combines the mathematical beauty of the Fibonacci sequence and the golden ratio into a practical computer science technique. While binary search is the go-to algorithm in most cases, Fibonacci search shines in environments where minimizing costly index calculations and sequential access optimizations matter. Understanding this algorithm not only enhances your problem-solving toolkit but also deepens appreciation for how mathematics and computing harmonize.
