Exponential search
Binary search needs to know where the list ends before it can look in the middle. Exponential search does not: it gallops forward in ever larger steps until it overshoots the target, then binary-searches the last step. That makes it ideal for lists of unknown length, and fast for values near the start.
The idea
Check the value at place 1, then 2, 4, 8, 16 and so on, each place twice the one before. As long as the value there is smaller than the target, the target must be further on. The first time a value is not smaller, the target is trapped: it lies after the previous place checked and no later than this one. That stretch is sorted, so a binary search finds the target, or shows it is missing.
An example
Search 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 for 23. Place 1 holds 2, place 2 holds 5, place 4 holds 12, all smaller. Place 8 holds 56, which is larger, so 23 can only be at places 5 to 7. Binary search checks the middle of those, place 6, and finds 23: 5 comparisons, where plain binary search needs 3. Searching the same list for 12 stops at place 4 after 3 comparisons, one fewer than binary search, and 2 is found at place 1 with a single comparison.
How many comparisons
For a target at place i, the doubling stops after about log₂ i steps, and it leaves a stretch of fewer than i places, which binary search covers in about log₂ i more. So the search costs about 2 log₂ i comparisons, whatever the length of the list. When the target is near the start that beats binary search, which always pays about log₂ n. When it is near the end, exponential search pays up to about twice as much. For 40 values the app averages about 3 comparisons for the first five places and about 9 for the last five, against about 4.6 for binary search.
Unknown length, and galloping
Jon Bentley and Andrew Yao described this doubling strategy in 1976 for unbounded searching: finding a value in a sorted sequence with no known end, such as an infinite list or a stream you can only probe. The same idea speeds up merging. When one of two sorted runs keeps winning, Timsort switches to galloping: it looks 1, 2, 4, 8 places ahead in the other run to find where the next value goes, instead of stepping one place at a time.
Explore it
Open the app, choose a value in Search for, and press Step. Each look at place 1, 2, 4, 8 and so on is highlighted; once a value is not smaller, the stretch between the last two places is shaded and binary search takes over. Search for a small value and then a large one, and compare the count with the binary search tile.
Frequently asked questions
What is the time complexity of exponential search?
O(log i) for a target at place i, so at most O(log n) for a list of n values. It needs O(1) extra memory and a sorted list.
What is the difference between exponential search and binary search?
Binary search starts with the whole list and needs its length. Exponential search first finds a stretch that contains the target by doubling, then binary-searches only that stretch. It is faster when the target is near the start and works without knowing the length.
Why double the step and not add a fixed amount?
Adding a fixed step is jump search, which needs about n divided by the step looks to get across the list. Doubling reaches place i in about log₂ i looks, and the stretch it leaves is never more than twice too large, so the binary search afterwards stays short.
Where is exponential search used?
In searching unbounded or very long sorted data, in merging sorted runs (galloping in Timsort), and in finding the first place where a condition becomes true when no upper limit is known.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Try exponential search