Fibonacci Search
A comparison-based search technique that uses Fibonacci numbers to divide the array into unequal parts. It's similar to binary search but divides the array using Fibonacci numbers instead of dividing it in half.
Visualization
Details
Analogy
Imagine searching for a book on a shelf, but instead of dividing the shelf in half each time (binary search), you divide it according to the golden ratio (approximately 0.618). This is what Fibonacci search does - it uses Fibonacci numbers, which approximate the golden ratio, to determine where to look next.
Purpose
To search sorted arrays efficiently using Fibonacci numbers for division. It's particularly useful when the cost of division operations is high, as it only uses addition and subtraction. The algorithm is based on the divide and conquer approach.
Use Cases
Useful on systems where division or multiplication operations are expensive (embedded systems, older processors). Good for large datasets stored on slow memory (tapes, disks) where sequential access is preferred. Used in financial algorithms that naturally involve Fibonacci sequences. Beneficial when you want to minimize the number of comparisons.
Algorithm Steps
fib2 = 0, fib1 = 1, fib = 1
while fib < n:
fib2 = fib1; fib1 = fib; fib = fib1 + fib2
offset = -1
while fib > 1:
i = min(offset + fib2, n-1)
if arr[i] < target: offset = i; fib = fib1; fib1 = fib2; fib2 = fib - fib1
elif arr[i] > target: fib = fib2; fib1 = fib1 - fib2; fib2 = fib - fib1
else: return i
if fib1 and arr[offset+1] == target: return offset+1
return -1
Explanation
What's Happening?
Initial sorted array: [10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100]. Starting Fibonacci search with search range [0, 10].
Code Implementation
def fibonacci_search(arr, target):
n = len(arr)
fib2, fib1 = 0, 1
fib = fib2 + fib1
while fib < n:
fib2 = fib1
fib1 = fib
fib = fib2 + fib1
offset = -1
while fib > 1:
i = min(offset + fib2, n - 1)
if arr[i] < target:
fib = fib1
fib1 = fib2
fib2 = fib - fib1
offset = i
elif arr[i] > target:
fib = fib2
fib1 = fib1 - fib2
fib2 = fib - fib1
else:
return i
if fib1 and offset + 1 < n and arr[offset + 1] == target:
return offset + 1
return -1