Binary search needs to know the array's length
before it can even pick its first probe, the midpoint. Exponential search (also called
galloping search) doesn't: it finds a range likely to contain the target by
starting at index 1 and doubling — 1, 2, 4, 8, 16… — until it either overshoots the target's
value or runs off the end of the array, then hands that range to an ordinary binary search.
That doubling phase costs only O(log i) probes, where i is the
target's actual index, not the array's length — so a target near the front of a huge array
costs roughly the same either way it's found, near-instantly, while binary search always pays
the full O(log n) no matter where the target sits. The catch, demonstrated below
with real counted probes rather than just asserted: for a target near the back of a
bounded array, the doubling phase is pure overhead paid on top of a binary search that's barely
smaller than the one binary search alone would have run — exponential search can cost
more total probes than plain binary search, not fewer.
The array below has 64 elements, values 0, 3, 6, …, 189, so both presets stay on
a size where the doubling steps (1, 2, 4, 8…) are easy to follow. early target
searches for a value near the front — the case exponential search is built for. late
target searches for a value near the back — the honest worst case, where the doubling
phase adds real cost instead of saving it. Step through either one and watch the probe counter
against what plain binary search would have needed on the identical array and target.
The doubling phase only needs to answer one question: "is the target still ahead of where
we're looking, or have we gone far enough?" — the same one-sided check binary search makes at
every probe, just walked forward instead of split in half. It stops as soon as
arr[bound] ≥ target (or it runs past the end of the array), at which point the
target — if it's present at all — must lie between the previous bound and the current one:
bound = 1
while bound < n and arr[bound] < target:
bound = bound * 2
# target (if present) is in [bound/2, min(bound, n-1)]Because arr[bound/2] < target was true on the previous check (or
bound/2 is 0, the array's very start) and arr[bound] ≥ target or
bound ran off the array, that range is guaranteed to hold the target if it's
anywhere in the array at all — exactly the invariant a binary search over
[bound/2, min(bound, n-1)] needs to finish the job. The number of doubling steps
to reach an index i is ⌈log₂ i⌉, and the binary
search that follows runs over a range of size roughly i too, so the total cost is
O(log i) — governed by where the target is, not by n.
That's also what makes this the standard technique for searching an unbounded or
streaming array, where n isn't known up front at all: the doubling phase
only ever needs to ask "is there a value here, and is it past the target?", which a length-free
data source (a sorted stream, a lazily-generated sequence) can still answer.
function exponentialSearch(arr, target) {
const n = arr.length;
if (n === 0) return -1;
let bound = 1;
while (bound < n && arr[bound] < target) {
bound *= 2;
}
const lo = Math.floor(bound / 2);
const hi = Math.min(bound, n - 1);
return binarySearch(arr, target, lo, hi);
}
function binarySearch(arr, target, lo, hi) {
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}The doubling phase is overhead, not a free head start — checked on this page's own
"late target" preset. Searching this exact 64-element array for 189 (index
63, the last element): exponential search takes 12 probes — six to walk the
bound up through 1, 2, 4, 8, 16, 32, then six more to binary-search the resulting 32-element
range — where plain binary search on the identical array and target needs only
7. The same array searched for 6 (index 2) instead flips the
result: exponential search takes 4 probes against binary search's
6. Same array, same code, opposite verdict — the win or loss depends entirely
on where the target happens to sit, not on anything the algorithm can detect or adapt to in
advance.
It doesn't help at all if the array's length is already known and the target's
position is unknown. The whole benefit is conditional on either (a) not knowing
n up front — an unbounded stream, where binary search literally cannot start
without it — or (b) having a real reason to expect the target lands near the front. Absent
either condition, a target's index is just as likely to land anywhere in the array, and the
doubling phase's extra probes are, on average, wasted relative to going straight to binary
search.
The doubling itself can overflow in a fixed-width integer language.
bound *= 2 run enough times on a genuinely huge or unbounded source will eventually
exceed a 32-bit integer's range in languages that use one (JavaScript's numbers don't have this
problem below 253). A production implementation searching a real unbounded stream
should guard the multiply or use a wider integer type.
O(log i) where i is the index the target is found at (or the
array's length, if absent) — strictly better than binary search's flat O(log
n) when the target is near the start, converges to roughly 2× binary
search's cost when the target is near the end, as the checked example above shows. Reach for
this over binary search specifically when the
array's length isn't available up front (an unbounded or streaming sorted source) — that's the
one case binary search can't handle at all — and treat "faster for front-loaded targets" as a
situational bonus on top of that, not the main reason to use it. See Choosing a Search Algorithm for how it stacks up
against the site's other ten Searching entries.