Exponential Search Algorithm

def binary_search(arr, left, right, target):
    """Helper function for binary search"""
    while left <= right:
        mid = (left + right) // 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):
    """
    Exponential Search Algorithm
    Time Complexity: O(log n)
    Space Complexity: O(1)
    Prerequisite: Array must be sorted
    """
    # Check if element is at first position
    if arr[0] == target:
        return 0
    
    # Find range for binary search by repeated doubling
    bound = 1
    while bound < len(arr) and arr[bound] < target:
        bound *= 2
    
    # Perform binary search in found range
    left = bound // 2
    right = min(bound, len(arr) - 1)
    
    return binary_search(arr, left, right, target)

# Example usage
sorted_array = [1, 2, 3, 4, 5, 8, 10, 15, 20, 26, 30, 31, 35, 42, 50, 65, 70, 88]
target = 42

result = exponential_search(sorted_array, target)
if result != -1:
    print(f"Element {target} found at index {result}")
else:
    print(f"Element {target} not found")

# Demonstrate the exponential bound finding
def exponential_search_verbose(arr, target):
    print(f"Searching for {target} in array of size {len(arr)}")
    
    if arr[0] == target:
        print(f"Found at index 0!")
        return 0
    
    bound = 1
    print(f"Starting exponential search with bound = {bound}")
    
    while bound < len(arr) and arr[bound] < target:
        print(f"arr[{bound}] = {arr[bound]} < {target}, doubling bound to {bound * 2}")
        bound *= 2
    
    left = bound // 2
    right = min(bound, len(arr) - 1)
    print(f"Range found: [{left}, {right}]")
    print(f"Performing binary search in range...")
    
    return binary_search(arr, left, right, target)

# Verbose example
print("\nVerbose search:")
exponential_search_verbose(sorted_array, 42)