Fibonacci Search
Divides the array at Fibonacci-number offsets using only addition and subtraction — historically useful on hardware without fast division.
- Category
- Searching
- Time complexity
- O(log n)
- Space complexity
- O(1)
Pseudocode
find smallest Fib ≥ n probe at offset + Fib(k−2) shrink the Fibonacci window toward the target side
Reference implementation
# fib numbers straddle n
i = min(offset + fibMM, n-1)
if a[i] < t: # move window up
fib, fibM, fibMM, offset = fibM, fibMM, fib-fibM, i
elif a[i] > t: # move window down
fib, fibM, fibMM = fibMM, fibM-fibMM, fib-fibM