How Exponential Search Works

Every search algorithm so far has assumed you know the size of the array before you start. But what if you're searching an unbounded stream — like scrolling through an infinite social media feed, or searching a massive sorted file where you genuinely don't know where it ends? You can't jump to "the middle" of something with no known end. Exponential Search solves exactly this problem: find a range that's guaranteed to contain the target first, then search inside it.

How Exponential Search Works

1. Start by checking index 1.
2. If the target is larger than that value, double the index — check index 2, then 4, then 8, then 16, and so on.
3. Stop doubling once you find an index whose value is greater than or equal to the target, or you exceed the array's bounds.
4. You've now found a range — from the last index before doubling to the current one — that must contain the target, if it exists.
5. Run Binary Search inside just that range.

Walking Through an Example

Search for 55 in [3, 8, 15, 23, 34, 41, 55, 62, 70, 81, 90, 100]:

• Check index 1: 8 → too small, double
• Check index 2: 15 → too small, double
• Check index 4: 34 → too small, double
• Check index 8: 70 → too big! The target must be between index 4 and index 8
• Run Binary Search on the range [4, 8] → finds 55 at index 6

Only 4 comparisons to find the range, then a small Binary Search inside it — and critically, none of this required knowing the array's total length in advance.

Java Implementation

public class ExponentialSearch {
    public static int exponentialSearch(int[] arr, int target) {
        int n = arr.length;
        if (arr[0] == target) {
            return 0;
        }

        // Find a range by doubling the index each time
        int i = 1;
        while (i < n && arr[i] <= target) {
            i *= 2;
        }

        // Binary search within the found range
        return binarySearch(arr, target, i / 2, Math.min(i, n - 1));
    }

    private static int binarySearch(int[] arr, int target, int low, int high) {
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {3, 8, 15, 23, 34, 41, 55, 62, 70, 81, 90, 100};
        System.out.println(exponentialSearch(arr, 55)); // Output: 6
    }
}

📝 Note

Exponential Search doesn't replace Binary Search — it's a way of quickly finding where to apply Binary Search when the array's size is unknown or effectively unbounded, like a stream or a very large file you don't want to measure up front.

Time Complexity

⚠️ Complexity Breakdown

Time: O(log n) — the doubling phase and the binary search phase are both logarithmic, so the total stays logarithmic.
Space: O(1)

Common Interview Questions

• Why is Exponential Search useful for unbounded or unknown-size data structures?
• Why is its overall time complexity still O(log n) even though it does two separate phases?
• How does the "doubling" phase relate to Binary Search's own halving logic?

The Takeaway

Exponential Search rounds out a common theme in this batch of posts: every search algorithm is really Binary Search's core idea, adapted for a specific constraint — unsorted data gets Linear Search, block-limited access gets Jump Search, evenly distributed values get Interpolation Search, and unknown size gets Exponential Search. The last one in this searching group, Ternary Search, takes a different angle entirely: dividing the search space into three parts instead of two.

➡️ Next in the Series

Ternary Search: Dividing Into Three Instead of Two

Happy learning!
— Team CodeElevateX 🚀