Back to Searching

Fibonacci Search Visualizer

Watch how Fibonacci Search uses Fibonacci numbers to divide the array and efficiently locate the target element.

Time: O(log n)
Space: O(1)
Requirement: Sorted Array
Fibonacci Division
Fibonacci Numbers: fibM=0, fibM1=0, fibM2=0 | Offset: -1 | Comparisons: 0
0
2
1
3
2
4
3
10
4
40
5
43
6
56
7
67
8
78
9
89
10
99
Target: 10 | Step: 1 of 0

Current Step:

Click Start to begin Fibonacci Search visualization

Fibonacci Search

Time Complexity:O(log n)
Space Complexity:O(1)
Division:Fibonacci
Operations:Addition only

Color Legend

Currently Checking
Offset Position
Target Found
Search Space

Fibonacci Numbers

The algorithm uses Fibonacci numbers to divide the array:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

Each division follows the golden ratio (φ ≈ 1.618), providing optimal search performance.

How It Works

  1. 1Find smallest Fibonacci ≥ array length
  2. 2Check element at offset + fibM2
  3. 3Eliminate sections using Fibonacci
  4. 4Continue until target found or exhausted

Python Implementation

def fibonacci_search(arr, target):
    n = len(arr)
    
    # Initialize Fibonacci numbers
    fib_m2 = 0  # (m-2)'th Fibonacci number
    fib_m1 = 1  # (m-1)'th Fibonacci number
    fib_m = fib_m2 + fib_m1  # m'th Fibonacci number
    
    # Find smallest Fibonacci number >= n
    while fib_m < n:
        fib_m2 = fib_m1
        fib_m1 = fib_m
        fib_m = fib_m2 + fib_m1
    
    offset = -1
    
    while fib_m > 1:
        # Calculate index to check
        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_m1 - fib_m2
            fib_m2 = fib_m - fib_m1
        else:
            return i
    
    # Check last element
    if fib_m1 and offset + 1 < n and arr[offset + 1] == target:
        return offset + 1
    
    return -1

Real-world Applications

  • • When multiplication/division is expensive
  • • Searching in sorted arrays efficiently
  • • Systems without floating-point arithmetic
  • • Optimal search with addition-only operations
  • • Embedded systems with limited CPU
  • • Mathematical sequence analysis