Exponential Search

#How does it work?

Exponential search first finds a range that must contain the target in a sorted array, then binary searches that range.

To find the range, a bound doubles 1, 2, 4, 8, … until the value at the bound passes the target. The target must lie between the last two bounds.

It is very fast when the target is near the start, and it works without knowing the array's length (unbounded or streaming data).

#Live animation

if a[0] == target: return 0
bound = 1
while bound < n and a[bound] < target: bound = bound · 2
lo = bound / 2; hi = min(bound, n - 1)
binary search in a[lo..hi]
return -1

#Step by step

1. 01Check the first element; if it is the target, done.
2. 02Start the bound at 1.
3. 03Double the bound while a[bound] is smaller than the target.
4. 04The target must be in [bound/2, bound].
5. 05Binary search that range.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

def binary_search(a: list[int], lo: int, hi: int, target: int) -> int:
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1


def exponential_search(a: list[int], target: int) -> int:
    """a must be sorted. Doubles a bound until it passes the target, then binary searches behind it."""
    if not a:
        return -1
    if a[0] == target:
        return 0
    bound = 1
    while bound < len(a) and a[bound] < target:
        bound *= 2
    return binary_search(a, bound // 2, min(bound, len(a) - 1), target)


numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print(exponential_search(numbers, 13))
print(exponential_search(numbers, 4))

#Complexity

i is the position of the target. Finding the bound takes log i steps, and the binary search within the range takes log i more. So a target near the start is found quickly however large n is. The worst case is O(log n), the same as binary search.

#When to use it?

Used on sorted data of unknown or huge size (unbounded lists, paged results) and when targets tend to be near the start. Also known as galloping search; Timsort uses it while merging runs.

#Practice

Log in to answer questions and save your progress.