Fibonacci Search
Splits a sorted array at Fibonacci numbers instead of halves, narrowing the range using only addition and subtraction.
How it works
Fibonacci search is a cousin of binary search for sorted arrays. Instead of splitting the range in half, it splits it using Fibonacci numbers (1, 1, 2, 3, 5, 8, 13, 21, …), where each number is the sum of the two before it.
It starts with the smallest Fibonacci number F(k) that is at least the array's length, and keeps the two before it, F(k-1) and F(k-2). Each step it checks the value F(k-2) positions past the part already ruled out (the offset):
- If it equals the target, it returns that index.
- If it is smaller, the target is further right: everything up to it is ruled out, and the range shrinks one Fibonacci step (to F(k-1)).
- If it is larger, the target is to its left: the range shrinks two Fibonacci steps (to F(k-2)).
Because F(k) = F(k-1) + F(k-2), the range always splits into two Fibonacci-sized parts, about 62% and 38% (the golden ratio). Moving to the next split only needs a subtraction, never a division. When the range runs out, it does one last check of the single value left, then returns -1.
When to use it
On today's computers, binary search is just as fast and simpler. Fibonacci search was designed for machines where division was slow, and for data on tape or disk, where its checks stay closer together than binary search's, so each read moves a shorter distance.
Complexity
The range shrinks by a factor of about 1.618 (the golden ratio) each step, so it needs about 1.44·log₂ n checks in the worst case, slightly more than binary search.
| Case | Time | When |
|---|---|---|
| Best | O(1) | The target is at the first point checked |
| Average | O(log n) | Each step keeps about 62% or 38% of the range |
| Worst | O(log n) | The target is found last, or isn't there at all |
| Extra space | Why |
|---|---|
| O(1) | It only keeps three Fibonacci numbers and the offset |
Implementations
function fibonacciSearch(array, target) {
const n = array.length;
let fibM2 = 0; // F(k-2)
let fibM1 = 1; // F(k-1)
let fib = 1; // F(k)
while (fib < n) {
fibM2 = fibM1;
fibM1 = fib;
fib = fibM1 + fibM2;
}
let offset = -1;
while (fib > 1) {
const i = Math.min(offset + fibM2, n - 1);
const value = array[i];
if (value === target) return i;
if (value < target) {
// Keep the right part: one Fibonacci step down
fib = fibM1;
fibM1 = fibM2;
fibM2 = fib - fibM1;
offset = i;
} else {
// Keep the left part: two Fibonacci steps down
fib = fibM2;
fibM1 = fibM1 - fibM2;
fibM2 = fib - fibM1;
}
}
if (fibM1 === 1 && offset + 1 < n && array[offset + 1] === target) {
return offset + 1;
}
return -1;
}
def fibonacci_search(array, target):
n = len(array)
fib_m2, fib_m1 = 0, 1 # F(k-2), F(k-1)
fib = 1 # F(k)
while fib < n:
fib_m2, fib_m1 = fib_m1, fib
fib = fib_m1 + fib_m2
offset = -1
while fib > 1:
i = min(offset + fib_m2, n - 1)
if array[i] == target:
return i
if array[i] < target:
fib, fib_m1 = fib_m1, fib_m2
fib_m2 = fib - fib_m1
offset = i
else:
fib = fib_m2
fib_m1 = fib_m1 - fib_m2
fib_m2 = fib - fib_m1
if fib_m1 == 1 and offset + 1 < n and array[offset + 1] == target:
return offset + 1
return -1
#include <algorithm>
#include <vector>
int fibonacciSearch(const std::vector<int>& a, int target) {
const int n = static_cast<int>(a.size());
int fibM2 = 0; // F(k-2)
int fibM1 = 1; // F(k-1)
int fib = 1; // F(k)
while (fib < n) {
fibM2 = fibM1;
fibM1 = fib;
fib = fibM1 + fibM2;
}
int offset = -1;
while (fib > 1) {
int i = std::min(offset + fibM2, n - 1);
if (a[i] == target) return i;
if (a[i] < target) {
fib = fibM1;
fibM1 = fibM2;
fibM2 = fib - fibM1;
offset = i;
} else {
fib = fibM2;
fibM1 = fibM1 - fibM2;
fibM2 = fib - fibM1;
}
}
if (fibM1 == 1 && offset + 1 < n && a[offset + 1] == target) {
return offset + 1;
}
return -1;
}