Fibonacci Search

Fibonacci search is a variant of binary search that uses Fibonacci numbers to divide the search interval. Instead of halving the range, it splits according to Fibonacci offsets.

It avoids division and relies only on addition and subtraction, which made it useful on early hardware.

Problem

Given a sorted array $A$ of length $n$ and a value $x$ , find an index $i$ such that

A[i] = x

If no such index exists, return $-1$ .

Key Idea

Let Fibonacci numbers be:

F_0 = 0,\quad F_1 = 1,\quad F_k = F_{k-1} + F_{k-2}

Find the smallest $F_k \ge n$ . This defines the initial search size.

At each step:

Compare with index offset by $F_{k-2}$
Reduce the search space using Fibonacci identities
Move the window accordingly

Algorithm

fibonacci_search(A, x):
    n = length(A)

    # find smallest Fibonacci number >= n
    fib2 = 0
    fib1 = 1
    fib = fib1 + fib2

    while fib < n:
        fib2 = fib1
        fib1 = fib
        fib = fib1 + fib2

    offset = -1

    while fib > 1:
        i = min(offset + fib2, n - 1)

        if A[i] < x:
            fib = fib1
            fib1 = fib2
            fib2 = fib - fib1
            offset = i
        else if A[i] > x:
            fib = fib2
            fib1 = fib1 - fib2
            fib2 = fib - fib1
        else:
            return i

    if fib1 and offset + 1 < n and A[offset + 1] == x:
        return offset + 1

    return -1

Example

Let

A = [1, 3, 5, 7, 9, 11, 13]

and

x = 9

Fibonacci numbers: $0, 1, 1, 2, 3, 5, 8$

Initial $fib = 8 \ge 7$

Probe positions shrink using offsets $5, 3, 2, 1$

The algorithm converges to index $4$ .

Correctness

The Fibonacci decomposition ensures that at each step:

The remaining search interval shrinks
The target, if present, remains within the reduced interval

The update rules preserve a valid search window analogous to binary search.

Complexity

case	time
all cases	$O(\log n)$

Space:

O(1)

Comparison with Binary Search

feature	binary search	fibonacci search
division	required	not used
operations	arithmetic	addition/subtraction
performance	slightly faster in modern systems	similar asymptotically

Binary search is generally preferred today due to simplicity and hardware efficiency.

When to Use

Systems where division is expensive
Sequential memory access patterns
Historical or educational contexts

Notes

Access pattern tends to move forward, which may help in some memory hierarchies
Rarely used in modern high level code

Implementation

def fibonacci_search(a, x):
    n = len(a)

    fib2, fib1 = 0, 1
    fib = fib1 + fib2

    while fib < n:
        fib2, fib1 = fib1, fib
        fib = fib1 + fib2

    offset = -1

    while fib > 1:
        i = min(offset + fib2, n - 1)

        if a[i] < x:
            fib, fib1, fib2 = fib1, fib2, fib - fib2
            offset = i
        elif a[i] > x:
            fib, fib1, fib2 = fib2, fib1 - fib2, fib - (fib1 - fib2)
        else:
            return i

    if fib1 and offset + 1 < n and a[offset + 1] == x:
        return offset + 1

    return -1

func FibonacciSearch(a []int, x int) int {
    n := len(a)

    fib2, fib1 := 0, 1
    fib := fib1 + fib2

    for fib < n {
        fib2, fib1 = fib1, fib
        fib = fib1 + fib2
    }

    offset := -1

    for fib > 1 {
        i := offset + fib2
        if i >= n {
            i = n - 1
        }

        if a[i] < x {
            fib, fib1, fib2 = fib1, fib2, fib-fib2
            offset = i
        } else if a[i] > x {
            fib, fib1, fib2 = fib2, fib1-fib2, fib-(fib1-fib2)
        } else {
            return i
        }
    }

    if fib1 == 1 && offset+1 < n && a[offset+1] == x {
        return offset + 1
    }

    return -1
}