Python实现插值查找

插值查找是一种改进的二分查找算法，适用于元素均匀分布的有序数组。它通过预测要查找的值在数组中的位置来缩小搜索范围。下面是使用Python实现插值查找的代码：

def interpolation_search(arr, x):
    # 获取数组的长度
    n = len(arr)
    
    # 初始化low和high指针
    low = 0
    high = n - 1

    while low <= high and x >= arr[low] and x <= arr[high]:
        # 如果数组中只有一个元素
        if low == high:
            if arr[low] == x:
                return low
            return -1
        
        # 使用插值公式预测位置
        pos = low + int((float(high - low) / (arr[high] - arr[low])) * (x - arr[low]))

        # 检查预测位置的元素
        if arr[pos] == x:
            return pos
        if arr[pos] < x:
            low = pos + 1
        else:
            high = pos - 1

    return -1

# 测试代码
arr = [10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47]
x = 18
result = interpolation_search(arr, x)
if result != -1:
    print(f"元素{x}在数组中的索引为{result}")
else:
    print("元素不在数组中")

这个代码实现了插值查找算法，并通过一个测试数组和测试值来演示其工作原理。你可以运行这段代码并根据需要进行调整。