Exponential

Exponential search algorithm targets a range of an input array in which it assumes that the required element must be present in and performs a binary search on that particular small range.

This algorithm is also known as doubling search or finger search.

It is similar to jump search in dividing the sorted input into multiple blocks and conducting a smaller scale search.

However, the difference occurs while performing computations to divide the blocks and the type of smaller scale search applied (jump search applies linear search and exponential search applies binary search).

Hence, this algorithm jumps exponentially in the powers of 2.

In simpler words, the search is performed on the blocks divided using pow(2, k) where k is an integer greater than or equal to 0.

Once the element at position pow(2, n) is greater than the key element, binary search is performed on the current block.

Exponential Search Algorithm

In the exponential search algorithm, the jump starts from the 1st index of the array. So we manually compare the first element as the first step in the algorithm.

Step 1 − Compare the first element in the array with the key, if a match is found return the 0th index.

Step 2 − Initialize i = 1 and compare the ith element of the array with the key to be search. If it matches return the index.

Step 3 − If the element does not match, jump through the array exponentially in the powers of 2. Therefore, now the algorithm compares the element present in the incremental position.

Step 4 − If the match is found, the index is returned. Otherwise Step 2 is repeated iteratively until the element at the incremental position becomes greater than the key to be searched.

Step 5 − Since the next increment has the higher element than the key and the input is sorted, the algorithm applies binary search algorithm on the current block.

Step 6 − The index at which the key is present is returned if the match is found; otherwise it is determined as an unsuccessful search.

pseudocode:

function exponentialSearch(arr, target):
    n = length(arr)
    
    if arr[0] == target:
        return 0  // Target found at the first position
    
    // Find range for binary search by repeated doubling
    i = 1
    while i < n and arr[i] <= target:
        i = i * 2
    
    // Perform binary search within the found range
    return binarySearch(arr, target, i / 2, min(i, n - 1))

function binarySearch(arr, target, start, end):
    while start <= end:
        mid = start + (end - start) / 2
        
        // Check if target is present at mid
        if arr[mid] == target:
            return mid
        
        // If target is greater, ignore left half
        else if arr[mid] < target:
            start = mid + 1
        
        // If target is smaller, ignore right half
        else:
            end = mid - 1
    
    // Target not found
    return -1

Analysis

Even though it is called Exponential search it does not perform searching in exponential time complexity.

But as we know, in this search algorithm, the basic search being performed is binary search.

Therefore, the time complexity of the exponential search algorithm will be the same as the binary search algorithm’s, O(log n).

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

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

// Example usage:
const arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
const target = 13;
const index = exponentialSearch(arr, target);
console.log(`Element ${target} is at index ${index}`);