Fibonacci Search

Fibonacci search finds a target in a sorted array the way binary search does — by repeatedly throwing away part of the array — but it never computes a midpoint. Instead it splits the search window using consecutive Fibonacci numbers, so every probe index is reached with addition and subtraction only. No //, no /. That makes it a quiet favorite on hardware where division is slow or unavailable.

Intuition

Binary search asks "what is the exact middle?" — and the middle needs a division. Fibonacci numbers give you a pre-baked set of split points instead. Because fibM = fibMm1 + fibMm2, a window of size fibM always breaks cleanly into a left part of size fibMm2 and a right part of size fibMm1. So the probe offset + fibMm2 is exactly the boundary between those two parts.

When the probe is too small, the answer is in the right (bigger) part of size fibMm1, so you shift the window down one Fibonacci step and move offset forward. When the probe is too big, the answer is in the left part of size fibMm2, so you shift the window down two steps and leave offset alone. Either way the window keeps shrinking along the Fibonacci sequence until it collapses.

Walk through it

Step through the animation on the right. The i pointer marks the current probe; the labels up top show the live Fibonacci window and the running offset. Dimmed cells are eliminated.

We start with fibMm2=5, fibMm1=8, fibM=13 (the smallest Fibonacci number at least 9) and offset=-1. The first probe is i = -1 + 5 = 4, and a[4] = 45 < 80, so the target is to the right: the window slides down one step to (3, 5, 8) and offset jumps to 4 — indices 0..4 go dim. Next probe is i = 4 + 3 = 7, and a[7] = 82 > 80, so we go left: the window slides down two steps to (1, 2, 3), offset stays 4, and index 7 rightward goes dim. Now i = 4 + 1 = 5, and a[5] = 50 < 80, go right again: window (1, 1, 2), offset = 5. The final probe is i = 5 + 1 = 6, and a[6] = 80 — a direct hit. We return 6, having used only additions and subtractions the whole way.

The code, line by line

def fib_search(a, x):
    n = len(a)
    fibMm2, fibMm1 = 0, 1
    fibM = fibMm2 + fibMm1
    while fibM < n:
        fibMm2, fibMm1 = fibMm1, fibM
        fibM = fibMm2 + fibMm1
    offset = -1
    while fibM > 1:
        i = min(offset + fibMm2, n - 1)
        if a[i] < x:
            fibM, fibMm1 = fibMm1, fibMm2
            fibMm2, offset = fibM - fibMm1, i
        elif a[i] > x:
            fibM, fibMm1 = fibMm2, fibMm1 - fibMm2
            fibMm2 = fibM - fibMm1
        else:
            return i
    return offset + 1 if fibMm1 and a[offset + 1] == x else -1

• Lines 5 to 7 grow the window until fibM is at least n. This is the only setup cost — a handful of additions.
• Line 8 seeds offset = -1, meaning "nothing consumed yet"; the first probe will be at index fibMm2 - 1 + 1.
• Line 10 is the heart: the probe is offset + fibMm2, clamped to the last valid index with min(..., n - 1). There is no division anywhere.
• Lines 11 to 13 handle "probe too small": shift the window down one step and advance offset to i, discarding the left part.
• Lines 14 to 16 handle "probe too big": shift the window down two steps and keep offset, discarding the right part.
• Line 19 is the final guard: when the loop ends with fibMm1 still set, one element may remain unchecked at offset + 1, so compare it directly before giving up with -1.

Complexity

Fibonacci search makes the same logarithmic number of probes as binary search — the window divides by the golden ratio (about 1.618) instead of exactly 2, so it is a small constant factor more comparisons. Its win is the arithmetic: only additions and subtractions, plus it probes indices closer to the front of the array first, which can be friendlier to a slow-to-seek storage medium.

When to use / pitfalls

Practice