While Binary Search assumes a fixed, finite interval, Exponential Search is designed for cases where the search space is potentially unbounded or where the target is likely to be found near the beginning of a massive dataset.

Exponential search works in two distinct phases. Let $i$ be the actual index of the target element in the array.

Phase 1 (The Jump): We start at index 1 and keep doubling the index ($1, 2, 4, 8, \dots, 2^k$) until we find an index $2^k$ such that $A[2^k] \ge \text{target}$ or we exceed the array bounds.

Since we double the index until $2^k \ge i$, the number of jumps is $\lceil \log_2 i \rceil$.

Phase 2 (The Refinement): Once the range $[2^{k-1}, 2^k]$ is identified, we perform a binary search within this range.

• The size of this range is $2^k - 2^{k-1} = 2^{k-1}$, which is proportional to $i$.
• Binary search on a range of size $O(i)$ takes $O(\log i)$.

Total Time Complexity: $O(\log i) + O(\log i) = O(\log i)$.

Space Complexity: $O(1)$ for the iterative implementation.

In pure Big-O notation, $\log i$ and $\log n$ look similar, but in practical theoretical applications, Exponential Search wins in three specific scenarios:

1. Searching in Unbounded or Infinite Arrays

   If you are searching for a value in a list where the size $n$ is unknown or infinite (e.g., a continuous stream of sorted data), Binary Search fails because it requires a "High" boundary to calculate the first midpoint $mid = (low + high) / 2$.

   Exponential search finds its own "High" boundary dynamically in $O(\log i)$ time, making it the standard choice for unbounded search problems.

2. Massive Arrays with "Front-Loaded" Targets

   Consider a dataset so large it doesn't fit in RAM (e.g., searching a multi-terabyte sorted file on disk).

   If $n = 10^{15}$ and the target $i = 1,000$:

   • Binary Search will still take $\approx \log_2(10^{15}) \approx 50$ probes, likely jumping across high-latency disk sectors or network nodes.
   • Exponential Search will take $\approx 2 \cdot \log_2(1,000) \approx 20$ probes, staying within the first few blocks of data.

3. Galloping in Merging Algorithms

   In Adaptive Merge Sort or when intersecting two sorted lists of vastly different sizes (size $m$ and $n$, where $m \ll n$), we use "Galloping" (another name for Exponential Search). Instead of doing a full binary search for every element of $m$ into $n$, we exponentially search to find the insertion point, which often results in $O(m \log(n/m))$ complexity rather than $O(m \log n)$.