Binary search splits the remaining range in
half, every time, via mid = (lo + hi) / 2. Fibonacci search solves the same
problem — find a value in a sorted array — but never divides anything, and never multiplies
either. Instead it picks the smallest Fibonacci number at least as large as the array, then
walks that number's two neighbors down the Fibonacci sequence one probe at a time, splitting
each remaining range not down the middle but at roughly the golden-ratio point
(≈38%/62%), using nothing but addition and subtraction to get there. That was the actual point
historically: on hardware (or storage media) where division was slow, expensive, or simply
unavailable, a search that only ever adds and subtracts was worth the uneven split. The
trade-off, demonstrated below with real counted probes: because the split isn't even, a target
that lands late in the array can cost more probes than plain binary search, not fewer —
the win is "no division," not "faster."
The array below has 20 elements, values 0, 3, 6, …, 57 — not itself a Fibonacci
number, which matters for the third preset. early target lands near the front,
where the golden-ratio split pays off. late target lands on the very last
element, the honest worst case where the uneven split costs extra probes. absent,
final check searches for a value that isn't in the array at all, but still triggers a
one-off check after the main loop — the mechanism behind this page's first pitfall.
Step through any of them and watch the probe counter against what plain binary search would
have needed on the identical array and target.
First, find the smallest Fibonacci number fibM that is at least the array's
length n, tracking its two predecessors fib1 and fib2
(so fib2 + fib1 = fibM) along the way — this loop only ever adds:
let fib2 = 0, fib1 = 1, fibM = fib2 + fib1; // fibM = 1
while (fibM < n) {
fib2 = fib1;
fib1 = fibM;
fibM = fib2 + fib1;
}Then probe at index offset + fib2 (clamped to the array's last index), where
offset starts at -1 and marks everything already ruled out below it.
If the probed value is too small, the whole lower Fibonacci number's worth of the range is
eliminated and the window shifts down by reusing fib1/fib2 as the
next smaller pair of Fibonacci numbers; if it's too large, the window shrinks from the
top the same way. Both updates are subtraction, never division:
if (arr[i] < target) { // shift down: keep the larger remaining piece
fibM = fib1; fib1 = fib2; fib2 = fibM - fib1;
offset = i;
} else if (arr[i] > target) { // shrink from the top: keep the smaller piece
fibM = fib2; fib1 = fib1 - fib2; fib2 = fibM - fib1;
}Because fib2 is always the smaller of the two neighboring Fibonacci
numbers, the very first probe lands at roughly fib2 / fibM of the way into the
array — and consecutive Fibonacci numbers converge to the golden ratio, so that's ≈38%, not
50%. Concretely, on this page's 20-element demo array the smallest covering Fibonacci number is
21 (with fib2 = 8), so the very first probe is at index 7 (8/21 ≈
38% in) — while binary search's first probe on the same 20 elements is at index
9, almost exactly the middle. That's the entire mechanism: every split is uneven by
design, in exchange for touching only + and -.
function fibonacciSearch(arr, target) {
const n = arr.length;
if (n === 0) return -1;
let fib2 = 0, fib1 = 1, fibM = fib2 + fib1;
while (fibM < n) {
fib2 = fib1;
fib1 = fibM;
fibM = fib2 + fib1;
}
let offset = -1;
while (fibM > 1) {
const i = Math.min(offset + fib2, n - 1);
if (arr[i] < target) {
fibM = fib1; fib1 = fib2; fib2 = fibM - fib1;
offset = i;
} else if (arr[i] > target) {
fibM = fib2; fib1 = fib1 - fib2; fib2 = fibM - fib1;
} else {
return i;
}
}
// one possible leftover candidate the loop's bookkeeping doesn't cover
if (fib1 && offset + 1 < n && arr[offset + 1] === target) {
return offset + 1;
}
return -1;
}The uneven split can cost more probes than binary search, not fewer — checked on
this page's own presets. Searching the 20-element demo array for 6 (index
2, the "early target" preset): Fibonacci search takes 2 probes against binary
search's 4 on the identical array and target. Searching the same array for
57 (index 19, the last element, "late target"): Fibonacci search takes
6 probes against binary search's 5. Same code, same array,
opposite verdict — the golden-ratio split front-loads its advantage the same way exponential
search's doubling phase does, so it costs real probes back on late-array targets. This was
never the point: the point is avoiding division, not beating binary search's probe count.
The final leftover candidate needs two guards, verified by deliberately removing
them. When the array's length isn't itself a Fibonacci number, the main loop's
Fibonacci bookkeeping can end with exactly one index — offset + 1 — still
untested, even though a simpler "eliminated below / eliminated above" tally would already call
the window empty. This page's own "absent, final check" preset shows it directly: searching the
20-element array for 10, the main loop narrows to an empty range by index 4 (its
last probe was less than target, eliminating up through index 3, right after a
previous probe had already eliminated index 4 and beyond) — yet the Fibonacci bookkeeping still
has one candidate left, index 4, and the algorithm correctly checks it before giving up.
Deliberately stripping both the fib1 guard and the offset + 1 < n
bounds check and rerunning against 1,845 array/target combinations (every length 0–40, every
target from just-below to just-above the array) produced zero wrong answers in
JavaScript — but 128 real out-of-bounds reads, silently masked only because
undefined === target is reliably false for a numeric target. A bounds-checked
language (Java, Python) throws on that same access; an unsafe one (raw C) reads whatever memory
happens to sit past the array and can return a wrong index by pure luck.
It still needs the array's length up front, unlike exponential search. Building the
initial Fibonacci table requires knowing n before the first probe, the same
requirement binary search has and exponential search specifically doesn't. Fibonacci search's
entire advantage over binary search is "no division," not "works without knowing the length" —
reach for exponential search, not this, when the array's size is genuinely unknown or
unbounded.
O(log n) — Fibonacci numbers grow exponentially at the same golden-ratio rate binary search's halving does, just with a different base, so the number of probes stays in the same asymptotic class as binary search, typically within a small constant factor either way, as the checked 2-vs-6 probe examples above show for one 20-element array. The only real reason to reach for this over binary search is hardware or storage where division is genuinely expensive relative to addition and subtraction — decreasingly common on modern general-purpose CPUs, which is why this stays a historical curiosity more than a default choice today. See Choosing a Search Algorithm for how it stacks up against the site's other ten Searching entries.