Exponential Search in JavaScript

When it comes to searching algorithms, we often think of the usual suspects like Binary Search or Linear Search. But what should we choose when we have a sorted, unbounded lists where the length is unknown or not easy to determine? Enter Exponential Search, a unique algorithm that doubles the range of search with each step, speeding up the process of locating a specific element.

In this short article, I'll get into the details of this intereseting algorithm, how it works, and how you can implement it using JavaScript.

What is Exponential Search?

Exponential Search, also known as doubling or galloping search, is an algorithm particularly useful for searching in unbounded or large sorted lists. It works by doubling the range of search until it finds a range where the desired value is likely to be. Once it narrows down a suitable range, it performs a binary search within that range to locate the exact element.

Note: Keep in mind that Exponential Search requires a sorted array to work effectively, as it leverages the sorted nature of the data to narrow down the search range quickly.

Implementing Exponential Search in JavaScript

Here's a step-by-step implementation of Exponential Search in JavaScript:

function exponentialSearch(arr, x) {
    if (arr[0] === x) return 0;
    
    // Find a range where the element might be present
    let i = 1;
    while (i < arr.length && arr[i] <= x) {
        i = i * 2;
    }

    // Perform binary search within the found range
    return binarySearch(arr, i / 2, Math.min(i, arr.length - 1), x);
}

function binarySearch(arr, left, right, x) {
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        
        if (arr[mid] === x) return mid;
        if (arr[mid] < x) left = mid + 1;
        else right = mid - 1;
    }

    return -1;
}

Here's how the code works:

1. If the target value is found at the first index, it returns 0.
2. Otherwise, it doubles the index until it finds a range where the element might be present.
3. Then it calls a binary search within the specified range.

You can now test the function with an example:

let arr = [2, 3, 4, 10, 40];
let x = 10;
let result = exponentialSearch(arr, x);
console.log("Element found at index " + result);

Time Complexity

The time complexity of Exponential Search is O(log i), where i is the position of the element in the array. This makes it a very efficient algorithm for sorted arrays, especially when the length is unknown or not easily determined.

Conclusion

Exponential Search is a robust and efficient algorithm that combines the best of both linear search and binary search. By doubling its range with each step, it narrows down the search space rapidly and then applies a binary search to precisely locate the target element. This combination makes it particularly useful for searching in large sorted lists where the length is not predetermined.