Exponential Search

Exponential search performs a quick initial scan using an exponential formula to create lower and upper bounds for the search. Then it performs a binary search where it has bounded the search.

Where do I use this?

This search is made for sorted arrays or sorted unbounded lists (otherwise you cannot bound the search).

Explanation

Like all searches you need to have something you're searching for. We will call this the key. That's step one. Now what we do is we scan through the list index in powers of 2. We will check indices 1,2,4,8,16,32,64 etc. if the value at the index is equal to the key we end the search. If the value at the index is less than the key we continue. Now if the value at the index is greater than the key we stop. Let's say for example at index 64 we found a value greater than the key. We know that the key is greater than the indices 1,2,4,8,16,32. So all we have to do is search between indices 32 and 64. Here you can use a binary search. Additionally if the index becomes larger than the length of the array we just search between the last power of two (that index was less than the key value) and the end of the array.

Time Complexity

Exponential search has a time complexity of $O(\log i)$, where $i$ is the position of the target element.

Implementation

def exponential_search(arr, target):
    n = len(arr)
    
    # Check if the target is present at the first index
    if arr[0] == target:
        return 0
    
    # Find the range where the target might be
    index = 1
    while index < n and arr[index] <= target:
        index *= 2
    
    # Perform binary search within the found range
    low = index // 2
    high = min(index, n - 1)
    
    return binary_search(arr, low, high, target)

def binary_search(arr, low, high, target):
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

# Example usage
if __name__ == "__main__":
    arr = [1, 2, 4, 5, 7, 9, 12, 15, 18, 21]
    target = 15
    result = exponential_search(arr, target)
    
    if result != -1:
        print("Element found at index {}".format(result))
    else:
        print("Element not found")