Exponential Search

Overview

Exponential search is an efficient algorithm for searching in sorted arrays, especially when the array size is unknown or potentially infinite. It combines two main steps:

1. Find the range where the target element may be present by exponentially increasing the search bounds.
2. Perform binary search within the found range.

Steps

1. Start with a subarray size of 1, compare its last element with the target x.
2. Double the subarray size (2, 4, 8, ...) until the last element of the subarray is greater than or equal to x.
3. Once an index i is found such that arr[i] >= x, the element must be present between i/2 and i (because the previous doubling did not find a greater value).
4. Perform binary search in the range [i/2, i].

Code

C++

class Solution {
public:
    int exponentialSearch(const vector<int>& arr, int x) {
        if (arr[0] == x) return 0;
        int i = 1;
        while (i < arr.size() && arr[i] <= x) i *= 2;
        int left = i / 2, right = min(i, (int)arr.size() - 1);
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == x) return mid;
            else if (arr[mid] < x) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }
};

Go

func exponentialSearch(arr []int, x int) int {
    if arr[0] == x {
        return 0
    }
    i := 1
    for i < len(arr) && arr[i] <= x {
        i *= 2
    }
    left, right := i/2, min(i, len(arr)-1)
    for left <= right {
        mid := left + (right-left)/2
        if arr[mid] == x {
            return mid
        } else if arr[mid] < x {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Java

class Solution {
    public int exponentialSearch(int[] arr, int x) {
        if (arr[0] == x) return 0;
        int i = 1;
        while (i < arr.length && arr[i] <= x) i *= 2;
        int left = i / 2, right = Math.min(i, arr.length - 1);
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == x) return mid;
            else if (arr[mid] < x) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }
}

Kotlin

class Solution {
    fun exponentialSearch(arr: IntArray, x: Int): Int {
        if (arr[0] == x) return 0
        var i = 1
        while (i < arr.size && arr[i] <= x) i *= 2
        var left = i / 2
        var right = minOf(i, arr.size - 1)
        while (left <= right) {
            val mid = left + (right - left) / 2
            if (arr[mid] == x) return mid
            else if (arr[mid] < x) left = mid + 1
            else right = mid - 1
        }
        return -1
    }
}

Python

class Solution:
    def exponential_search(self, arr: list[int], x: int) -> int:
        if arr[0] == x:
            return 0
        i = 1
        while i < len(arr) and arr[i] <= x:
            i *= 2
        left, right = i // 2, min(i, len(arr) - 1)
        while left <= right:
            mid = left + (right - left) // 2
            if arr[mid] == x:
                return mid
            elif arr[mid] < x:
                left = mid + 1
            else:
                right = mid - 1
        return -1

Rust

impl Solution {
    pub fn exponential_search(arr: &[i32], x: i32) -> i32 {
        if arr[0] == x {
            return 0;
        }
        let mut i = 1;
        while i < arr.len() && arr[i] <= x {
            i *= 2;
        }
        let (mut left, mut right) = (i / 2, std::cmp::min(i, arr.len() - 1));
        while left <= right {
            let mid = left + (right - left) / 2;
            if arr[mid] == x {
                return mid as i32;
            } else if arr[mid] < x {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        -1
    }
}

TypeScript

class Solution {
    exponentialSearch(arr: number[], x: number): number {
        if (arr[0] === x) return 0;
        let i = 1;
        while (i < arr.length && arr[i] <= x) i *= 2;
        let left = Math.floor(i / 2), right = Math.min(i, arr.length - 1);
        while (left <= right) {
            const mid = left + Math.floor((right - left) / 2);
            if (arr[mid] === x) return mid;
            else if (arr[mid] < x) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }
}

Complexity

• ⏰ Time complexity: O(log n) — Exponential search finds the range in O(log n), then binary search finds the element in O(log n).
• 🧺 Space complexity: O(1) — With iterative binary search, only constant extra space is used.

Applications

• Exponential search is particularly useful for unbounded searches, where the size of the array is infinite or unknown.
• It works better than binary search for bounded arrays, especially when the element to be searched is closer to the first element.

Related Problems

• [Find point of transition from 0 to 1 in an infinite sorted binary array](/cs/problems/find-point-of-transition-from-0-to-1-in-an-infinite-sorted-binary-array)
• [Find the position of an element in a sorted infinite array](/cs/problems/find-the-position-of-an-element-in-a-sorted-infinite-array)