Back to Searching

Exponential Search Visualizer

Watch how Exponential Search finds the range exponentially, then performs binary search within that range.

Time: O(log n)
Space: O(1)
Requirement: Sorted Array
Exponential + Binary
Current Bound: 1 | Phase: EXPONENTIAL | Comparisons: 0
0
1
👆
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
12
11
14
12
16
13
18
14
20
15
22
16
24
17
26
18
28
19
30
Target: 18 | Step: 1 of 0

Current Step:

Click Start to begin Exponential Search visualization

Exponential Search

Time Complexity:O(log n)
Space Complexity:O(1)
Best For:Unbounded Arrays
Type:Hybrid

Color Legend

Exponential Phase Range
Currently Checking
Binary Search Range
Target Found
Not in Search Range

How It Works

  1. 1Start with bound = 1
  2. 2Double bound until element ≥ target
  3. 3Set range [bound/2, bound]
  4. 4Perform binary search in range

Python Implementation

def exponential_search(arr, target):
    # If target is at first position
    if arr[0] == target:
        return 0
    
    # Find range for binary search
    bound = 1
    while bound < len(arr) and arr[bound] < target:
        bound *= 2
    
    # Binary search in found range
    left = bound // 2
    right = min(bound, len(arr) - 1)
    
    return binary_search(arr, target, left, right)

def binary_search(arr, target, left, right):
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Real-world Applications

  • • Searching in unbounded/infinite arrays
  • • When array size is unknown
  • • Searching in very large sorted datasets
  • • Finding elements near the beginning
  • • Memory-mapped file searching
  • • Network packet searching