DSAverse

Initializing Sorting Algorithms...

Sorting Algorithm

Binary Tree

Graph Traversal

Preparing interactive visualizations for optimal learning experience...

DSAverse

Initializing Sorting Algorithms...

Sorting Algorithm

Binary Tree

Graph Traversal

Preparing interactive visualizations for optimal learning experience...

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

Target Value: 10

Fibonacci Numbers: fibM=0, fibM1=0, fibM2=0 | Offset: -1 | Comparisons: 0

Animation Speed: Normal

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

1Find smallest Fibonacci ≥ array length
2Check element at offset + fibM2
3Eliminate sections using Fibonacci
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

DSAverse

Initializing Sorting Algorithms...

Sorting Algorithm

Binary Tree

Graph Traversal

Preparing interactive visualizations for optimal learning experience...

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

Target Value: 10

Fibonacci Numbers: fibM=0, fibM1=0, fibM2=0 | Offset: -1 | Comparisons: 0

Animation Speed: Normal

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

1Find smallest Fibonacci ≥ array length
2Check element at offset + fibM2
3Eliminate sections using Fibonacci
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