Algorithm Guidecomplexity: O(log n)

Fibonacci Search

Partitions the range using Fibonacci numbers. Because it computes indices with only addition and subtraction — no division — it can beat binary search on hardware where division is expensive or where cache-friendly access matters.

01Fibonacci Search

Explore How It Works

Starting Fibonacci search. It carves the range by Fibonacci numbers, choosing each probe with additions and subtractions only — no division.

The first probe is index 4, holding 45. Compare it with the target 89.

45 is smaller than 89. Keep only the right side and step the Fibonacci numbers down one.

The next probe is index 7, holding 78.

78 also falls short of 89. Move right again and shrink the range further.

This probe lands on 98, at the end of the array.

98 is larger than 89. The target is to the left, so step the Fibonacci numbers down two and cut the range sharply.

The probed slot holds 89 — a match, on the fourth probe.

Search complete · 89 sits at index 8. It replaces binary search where division is expensive, as on embedded hardware.

Live Python

1def fibonacci_search(arr, target):

2 n = len(arr)

3 fib_m2 = 0

4 fib_m1 = 1

5 fib_m = fib_m2 + fib_m1

# F(k-2): 5

6 while fib_m < n:

# F(k-1): 8

7 fib_m2 = fib_m1

# F(k): 13

8 fib_m1 = fib_m

9 fib_m = fib_m2 + fib_m1

10 offset = -1

11 while fib_m > 1:

12 i = min(offset + fib_m2, n - 1)

13 if arr[i] < target:

14 fib_m = fib_m1

15 fib_m1 = fib_m2

16 fib_m2 = fib_m - fib_m1

17 offset = i

18 elif arr[i] > target:

19 fib_m = fib_m2

20 fib_m1 = fib_m1 - fib_m2

21 fib_m2 = fib_m - fib_m1

22 else:

23 return i

24 return -1

1 / 9

02 Understand It Simply

For Everyone

🔑How It Works

Divides the range at Fibonacci numbers, narrowing it with additions and subtractions only, never a division.

💡In Plain Words

Splits the range with the Fibonacci sequence.

It uses only addition and subtraction (no division), which helps on certain hardware.

📍Where It's Used

–Environments where division is costly
–cache-friendly access

03 Python Implementation

A clean, readable reference implementation of the core logic of Fibonacci Search.

core_implementation.py

def fibonacci_search(arr, target):
    n = len(arr)
    fib_m2, fib_m1 = 0, 1
    fib_m = fib_m2 + fib_m1
    while fib_m < n:
        fib_m2, fib_m1 = fib_m1, fib_m
        fib_m = fib_m2 + fib_m1
    offset = -1
    while fib_m > 1:
        i = min(offset + fib_m2, n - 1)
        if arr[i] < target:
            fib_m, fib_m1 = fib_m1, fib_m2
            fib_m2 = fib_m - fib_m1
            offset = i
        elif arr[i] > target:
            fib_m = fib_m2
            fib_m1 -= fib_m2
            fib_m2 = fib_m - fib_m1
        else:
            return i
    return -1