Exponential Search

Doubles a bound (1, 2, 4, 8…) until it passes the target, then binary-searches that final range. Great for unbounded or infinite streams where the length is unknown.

Category: Searching
Time complexity: O(log n)
Space complexity: O(1)

Pseudocode

bound ← 1
while a[bound] < t: bound ×= 2
binary search in [bound/2, bound]
return index

Reference implementation

bound = 1
while bound &lt; n and a[bound] &lt; t:
    bound *= 2
return binary_search(
    a, bound // 2, min(bound, n-1), t)

Open the interactive Exponential Search visualisation →