Overview
Fibonacci Search narrows a sorted range using Fibonacci numbers as the split points instead of halving. Every probe position is reached by adding two previous Fibonacci numbers, so the algorithm needs no division and no multiplication — only addition and subtraction.
That was a real advantage on hardware where division cost many times what addition did. It has a second, longer-lived property: the two candidate intervals it can move into are of unequal size, and it always steps by the smaller amount, so its memory access pattern is more localised than binary search's — which is why it still appears in contexts where the data sits on tape, disk, or anything with a punishing seek.
How Fibonacci Search works
- Find the smallest Fibonacci number F(k) that is greater than or equal to the array length.
- Keep the two Fibonacci numbers below it and use them to compute a probe index near the front of the current range.
- Compare the target with the value at that probe. On a match, stop.
- If the target is larger, move the offset up to the probe and shift the Fibonacci triple down by one; if smaller, keep the offset and shift the triple down by two.
- Repeat until the Fibonacci numbers reach the bottom of the sequence, then check the single remaining element.
When to use it
- Search on media with expensive non-sequential access — tape, spinning disk, or paged data — where locality beats round count.
- Embedded or fixed-point environments where integer division is slow or unavailable.
- As a companion to the golden-section search, its continuous cousin used for optimising unimodal functions.
- Rarely worth it in ordinary in-memory code — binary search is simpler and division is cheap on modern CPUs.
Complexity analysis
Time is O(log n): each step drops the range to roughly 1/φ of its size, where φ ≈ 1.618, giving log_φ n ≈ 1.44·log₂ n steps. So it needs a few more probes than binary search but each is computed with additions alone. Space is O(1) — the three Fibonacci numbers and an offset. The array must be sorted and randomly indexable, the same precondition binary search has.
Frequently asked questions
Why Fibonacci numbers specifically?
Because F(k) = F(k−1) + F(k−2) means every index you need is a sum of numbers you already hold. The split ratio that falls out is the golden ratio, which is also the ratio that makes the two possible next intervals reusable without recomputing anything.
Is it faster than binary search?
Not in comparison count — it makes about 44% more probes. It can still win on hardware where a division costs more than that difference, or where its tighter access locality avoids cache misses and disk seeks.
Does the array length have to be a Fibonacci number?
No. The algorithm picks the first Fibonacci number at least as large as the length and clamps any probe that lands past the end, so arbitrary lengths work without padding.