Interpolation Search

Algorithms

Interpolation search is an improved variant of binary search for uniformly distributed sorted arrays. It estimates the position of the target value based on the value of the endpoints.

Algorithm

Instead of always checking the middle element, interpolation search estimates the position using the formula:

p os = l o w + \frac{( t a r g e t - a rr [ l o w ]) \times ( hi g h - l o w )}{a rr [ hi g h ] - a rr [ l o w ]}

Time Complexity

For uniformly distributed data, interpolation search has an average time complexity of $O (lo g lo g n)$ . In the worst case, it can be $O (n)$ .

Implementation

def interpolation_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high and target >= arr[low] and target <= arr[high]:
        # Estimate the position of the target value
        pos = low + ((target - arr[low]) * (high - low) // (arr[high] - arr[low]))
        
        # Check if the estimated position is the target
        if arr[pos] == target:
            return pos
        elif arr[pos] < target:
            low = pos + 1
        else:
            high = pos - 1
    
    return -1

# Example usage
if __name__ == "__main__":
    arr = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
    target = 70
    result = interpolation_search(arr, target)
    
    if result != -1:
        print("Element found at index {}".format(result))
    else:
        print("Element not found")