Exponential Search

Color Legend

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