Unbounded Arrays | Doubling Phase + Binary Search | O(log n)
Imagine flipping through a fat dictionary to find a word near the front. You don't turn one page at a time, and you don't open it dead-centre either. You jump a little, then jump twice as far, then twice as far again — until you've clearly gone past the word — and only then do you settle down and search carefully in the short stretch you just leapt over. That two-gear strategy is exponential search: sprint to get into the neighbourhood, then walk to pin down the exact spot.
The list has to be sorted, like page numbers. Say your value sits at position $k$ in an array of size $n$. In the first gear you probe positions $1, 2, 4, 8, 16, \ldots$ — each step doubling the index — and you stop the instant a value overshoots your target (or you run off the end). Because you double, it only takes about $\log_2 k$ jumps to fly past position $k$. The pay-off: you never needed to know how big the array was. That is exactly why exponential search shines on unbounded or unknown-length lists, where plain binary search can't even start because it needs $n$ up front.
A quick number makes the win concrete. In a million-element array, binary search always spends about $\log_2(10^6) \approx 20$ probes. If your target is way out at $k \approx 1000$, exponential search isn't faster — it doubles to 1024 in ten steps, then binary-searches a 512-wide window in nine more, roughly the same 20. But if the target is near the front at $k = 8$, exponential search needs only about $3 + 3 = 6$ probes while binary search still grinds through all 20. The closer the target is to the start, the bigger the head start.
Try this with the controls above. First, drag the n slider from small to large and notice that the search cost grows only like $\log n$, not like $n$ — the bars pile up but the work barely moves. Second, switch the preset to Sorted: exponential search is only correct on ordered data, so this is the case the doubling-then-bracket logic in the pseudo-code is built for. Third, read down the pseudo-code panel line by line and trace where $i$ would land for a target near the front versus one near the end — that single difference is the whole reason the algorithm exists.
| Symbol | Meaning |
|---|---|
| n | Input size |
| T(n) | Time complexity function |
| h | Height or depth of structure |
| k | Key or rank parameter |
| W(n) | Worst-case complexity |
| A(n) | Average-case complexity |
X Exponential Search is only for infinite arrays.
O It also improves performance on finite arrays when target is likely near the beginning.
X It requires O(log n) doubling steps in all cases.
O Only O(log k) steps where k is target position. For target near start, far fewer than log n.
X Doubling always gives range [i/2, i] of size exactly i/2.
O Range size is i - i/2 = i/2 (floor). For i=1: range [0,1] size 2. Binary search within this range, not just i/2 elements.
X Forgetting to check array bounds before accessing A[i].
O For finite arrays: check i < n. For infinite/unbounded: check A[i] exists. Out-of-bounds access is a common crash.
X Using i = i+1 instead of i = i*2 in doubling phase.
O i = i+1 gives linear O(k) steps. Must double: i = i*2 or i <<= 1 to get O(log k).
X Not checking A[0] first before entering loop.
O A[0] check is the base case. Without it, the loop condition may skip index 0 if the target happens to equal A[0].