Exponential Search

On sorted data, doubles an index (1, 2, 4, 8 …) until it overshoots the target, then runs a binary search inside the last bracket. Finds the range in O(log i) where i is the answer index — ideal for unbounded or front-loaded data.

Best

O(1)

Average

O(log n)

Worst

O(log n)

Space

O(1)