AlgoViz: Interactive Algorithm Visualization Tool

Exponential Search

Category: Searching | Time: O(log n) | Space: O(1)

Input Data

Visualization

Visual representation of the data structure

Enter an algorithm and input to start visualization.

About Exponential Search

An algorithm used for searching in sorted, unbounded arrays. It involves two steps: first finding a range where the element could be, and then performing a binary search within that range.

Code Editor

The code is for reference. Editing it won't affect the visualization.

function exponentialSearch(arr, x) {
    let n = arr.length;
    if (arr[0] == x)
        return 0;
    let i = 1;
    while (i < n && arr[i] <= x)
        i = i * 2;
    return binarySearch(arr, i / 2, Math.min(i, n - 1), x);
}

function binarySearch(arr, l, r, x) {
    if (r >= l) {
        let mid = l + Math.floor((r - l) / 2);
        if (arr[mid] == x)
            return mid;
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);
        return binarySearch(arr, mid + 1, r, x);
    }
    return -1;
}

What is Exponential Search?

How does Exponential Search work?

What is the time complexity?

Why is it useful for unbounded arrays?

What is the space complexity?

When is it faster than Binary Search on a bounded array?

Is a sorted array required?

How does it differ from Interpolation Search?

Can it be implemented without recursion?

What is another name for Exponential Search?

Where can I learn more?