1. One-Liner
Fibonacci search partitions a sorted array using Fibonacci numbers instead of halving, so the probe position moves by Fibonacci offsets—historically friendly to tape-like sequential access.
2. The Problem It Solves
Same as binary search (find in sorted array), but with a different split schedule: only one new element is compared when shrinking from one Fibonacci-sized window to the next—useful when large moves are cheaper in a specific memory model (conceptual).
3. The Core Idea
Choose the smallest Fibonacci F_k ≥ n, start with two Fibonacci pointers (fibK2, fibK1) summing to F_k, and compare at offset fibK2 from the left of the current window; shrink using Fibonacci recurrence backward.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | Precompute Fibonacci until F_m ≥ n; set fibM2 = F_{m-2}, fibM1 = F_{m-1} (names vary). |
| 2 | Offset idx = min(offset + fibM2, n-1); compare arr[idx] to target. |
| 3 | If equal → return; if less → drop left part and reduce Fib pair; if greater → drop right part. |
| 4 | Last steps may require linear cleanup on tiny residual. |
5. Dry Run Example
Array: [1, 3, 5, 7, 9, 11, 13, 15] (n=8), Fibonacci 8,13,21... → use F_6=8: window size 8.
| Trace sketch | On [1,3,5,7,9,11,13,15] searching for 7, the first probe lands at an index about offset + F_{k-2}; each comparison shrinks the active window using the Fibonacci recurrence until the value matches or one element remains. |
|---|
Key invariant: each step updates the (fibM, fibM−1, fibM−2) triple so the remaining interval size follows Fibonacci descent.
6. Key Properties
| Property | Detail |
|---|---|
| Time | O(log n) comparisons (same class as binary). |
| Space | O(1) with iterative Fibonacci walk. |
| Note | More complex to code than binary; same asymptotics. |
7. Where It Is Used
| Company / domain | Use |
|---|---|
| Historical / educational | Tape seek analogies, curriculum. |
| Embedded | Rare; binary dominates in practice. |
8. Interview Tips
Know Fibonacci gap update rules and edge indices. Be honest: binary is simpler; Fibonacci is a pattern question.
9. Comparison with Other Algorithms
| Algorithm | Split |
|---|---|
| Binary | Halves: 1/2, 1/2 |
| Fibonacci | F_{i-2} / F_i style ratios |
| Golden ratio | Related limiting ratio φ |
10. Complexity
| Time | Space |
|---|---|
| O(log n) | O(1) |
Implementation Example (PYTHON)
def fibonacci_search(arr, target):
n = len(arr)
if n == 0:
return -1
fib_mm2, fib_mm1 = 0, 1
fib_m = fib_mm2 + fib_mm1
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] < target:
fib_m = fib_mm1
fib_mm1 = fib_mm2
fib_mm2 = fib_m - fib_mm1
offset = i
elif arr[i] > target:
fib_m = fib_mm2
fib_mm1 = fib_mm1 - fib_mm2
fib_mm2 = fib_m - fib_mm1
else:
return i
if fib_mm1 and offset + 1 < n and arr[offset + 1] == target:
return offset + 1
return -1