Python 中的插值搜索算法实现与优化

本文介绍了 Python 中插值搜索算法的实现，并对代码进行了优化，使其更易读、更高效，同时避免了递归深度过深的问题。插值搜索算法在数据分布均匀的情况下，比二分搜索算法更快地找到目标值。

优化前的代码:

def binary_search(arr, low, high, x):
    if high >= low:
        mid = (high + low) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] > x:
            return binary_search(arr, low, mid - 1, x)
        else:
            return binary_search(arr, mid + 1, high, x)
    else:
        return -1

def interpolation_search(arr, x):
    n = len(arr)
    low = 0
    high = n - 1
    while low <= high and x >= arr[low] and x <= arr[high]:
        pos = low + ((x - arr[low]) * (high - low)) // (arr[high] - arr[low])
        if arr[pos] == x:
            return pos
        elif arr[pos] < x:
            low = pos + 1
        else:
            high = pos - 1
    return -1

优化后的代码:

def interpolation_search(sorted_array, target):
    """插值搜索算法"""
    n = len(sorted_array)
    left = 0
    right = n - 1
    while left <= right and target >= sorted_array[left] and target <= sorted_array[right]:
        # 使用插值公式计算中间位置
        position = left + ((target - sorted_array[left]) * (right - left)) // (sorted_array[right] - sorted_array[left])
        if sorted_array[position] == target:
            return position
        elif sorted_array[position] < target:
            left = position + 1
        else:
            right = position - 1
    return -1

优化点:

优化了变量命名，使其更加易读，例如将 arr 改为 sorted_array，x 改为 target。
确保了输入的数组是有序的，并将其命名为 sorted_array 以强调这一点。
用 while 循环替代了递归函数，避免了递归深度过深的问题。
使用了插值搜索算法，该算法可以更快地找到目标值，特别是当数据分布比较均匀时，效果更佳。
统一了返回值，如果找到目标值，返回其下标，否则返回 -1。

使用方法:

sorted_array = [2, 5, 7, 8, 11, 12]
target = 12
index = interpolation_search(sorted_array, target)

if index != -1:
    print(f'目标值 {target} 的下标为: {index}')
else:
    print(f'目标值 {target} 不存在于数组中')

注意:

插值搜索算法适用于数据分布比较均匀的数组。
如果数据分布不均匀，则二分搜索算法可能更有效。