Fibonacci Search

Fibonacci search reaches the same O(log n) as binary search but gets there a different way. It first finds the smallest Fibonacci number that is at least the length of the array, then keeps three consecutive Fibonacci numbers on hand. Each probe lands not at the midpoint but at a Fibonacci offset into the current window. On a miss, it simply shifts that trio of Fibonacci numbers one place down — an operation that only ever adds and subtracts — and the window shrinks by roughly the golden ratio, about 1.618 times, each round.

The point of all that Fibonacci bookkeeping is what it avoids: there is no (lo + hi) / 2, no division, and no multiplication anywhere in the loop. On early computers, and on some embedded and older hardware since, division was markedly slower than addition, so a search that replaced every midpoint with a few additions could be a real win. It also touches memory in unequal steps that tend to stay closer to the previous probe than binary search’s jumps do, which can be gentler on systems where nearby data is cheaper to reach. The trade is a little more state to carry and slightly more probes on average than binary search.

Watch the shaded window step inward by Fibonacci-sized amounts rather than halving cleanly. Type a value into the search box to look for something specific, or leave it empty and let the Target menu pick one that is present or falls in a gap. Data switches between numbers and words, and New array deals a fresh sorted set.