Overview

The exponential search algorithm is useful for searching in a sorted array, particularly when the size of the array is large. It works by first finding a range where the element may exist and then performing a binary search within that range. This algorithm is efficient for unbounded or infinite lists.

Program Structure

def binary_search(arr, left, right, target):
    """Perform binary search on a sorted array."""
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

def exponential_search(arr, target):
    """Perform exponential search on a sorted array."""
    if arr[0] == target:
        return 0
    
    # Find the range for the binary search
    index = 1
    while index < len(arr) and arr[index] <= target:
        index *= 2
    
    # Call binary search for the found range
    return binary_search(arr, index // 2, min(index, len(arr) - 1), target)

# Example usage
if __name__ == "__main__":
    sorted_array = [2, 3, 4, 10, 40, 50, 60, 70, 80, 90]
    target_value = 10
    result = exponential_search(sorted_array, target_value)
    
    if result != -1:
        print(f"Element found at index: {result}")
    else:
        print("Element not found in the array.")

Explanation

The program consists of two main functions: binary_search and exponential_search.

1. Binary Search Function

– The binary_search function takes a sorted array arr, the left and right indices of the current search space, and the target value to find.
– It iteratively checks the middle element of the search space, adjusting the search boundaries until it either finds the target or concludes it’s not in the array.

2. Exponential Search Function

– The exponential_search function first checks if the first element is the target. If so, it returns 0.
– It then finds the range in which the target may exist by repeatedly doubling the index until the target is smaller than the current element or the end of the array is reached.
– Finally, it calls the binary_search function on the determined range to locate the target.

Example Usage

In the example provided, a sorted array is defined, and the target value is set to 10. The result of the search is printed to the console, indicating whether the target was found and its index.

Conclusion

The exponential search algorithm is a powerful method for efficiently finding elements in sorted arrays, especially for large datasets. By combining the strengths of exponential range searching and binary search, it minimizes the number of comparisons needed to find the target element.