插值查找是一种改进的二分查找算法,适用于元素均匀分布的有序数组。它通过预测要查找的值在数组中的位置来缩小搜索范围。下面是使用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("元素不在数组中")
这个代码实现了插值查找算法,并通过一个测试数组和测试值来演示其工作原理。你可以运行这段代码并根据需要进行调整。