# Fibonacci Search

# 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

```id="fib-1"
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

```id="py-fib"
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
```

```id="go-fib"
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
}
```