Interpolation Search Algorithm

def interpolation_search(arr, target):
    """
    Interpolation Search Algorithm
    Time Complexity: O(log log n) for uniformly distributed data
                    O(n) worst case
    Space Complexity: O(1)
    Prerequisite: Array must be sorted and uniformly distributed for best performance
    """
    left = 0
    right = len(arr) - 1
    
    while left <= right and target >= arr[left] and target <= arr[right]:
        # Handle single element
        if left == right:
            if arr[left] == target:
                return left
            return -1
        
        # Calculate interpolated position
        # Formula: left + [(target - arr[left]) / (arr[right] - arr[left])] * (right - left)
        pos = left + int(((target - arr[left]) / (arr[right] - arr[left])) * (right - left))
        
        # Ensure pos is within bounds
        pos = max(left, min(pos, right))
        
        if arr[pos] == target:
            return pos
        elif arr[pos] < target:
            left = pos + 1
        else:
            right = pos - 1
    
    return -1

# Example usage
uniform_array = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
target = 50

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

# Performance comparison
import time

# Uniform distribution - best case
uniform_data = list(range(1, 1000001, 1))
start_time = time.time()
interpolation_search(uniform_data, 500000)
print(f"Uniform data search time: {time.time() - start_time:.6f} seconds")