插值查找（Interpolation Search）

# /*
# 插值查找（Interpolation Search）
# --------------------------------------------------------
# 原理：
# 在有序序列中，通过估算目标值可能的位置来加速查找，
# 类似于在电话簿中根据姓名首字母猜测位置。
# 适合“均匀分布”的数据，性能优于二分查找。
# */

def interpolation_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high and target >= arr[low] and target <= arr[high]:
        # 避免除以零
        if arr[high] == arr[low]:
            if arr[low] == target:
                return low
            else:
                return -1

        # 估算位置
        pos = low + ((target - arr[low]) * (high - low)) // (arr[high] - arr[low])

        if arr[pos] == target:
            return pos
        elif arr[pos] < target:
            low = pos + 1
        else:
            high = pos - 1

    return -1


# 示例演示（必须是有序且均匀分布的列表）
data = [10, 20, 30, 40, 50, 60, 70]
print("数据：", data)

pos = interpolation_search(data, 50)
print("查找 50 的位置:", pos)

pos = interpolation_search(data, 25)
print("查找 25 的位置:", pos)

# --------------------------------------------------------
# 关键要点总结：
# 1) 仅适用于“有序且数值分布均匀”的序列；
# 2) 利用目标值比例估算可能位置；
# 3) 时间复杂度：均匀分布时 O(log log n)，最坏 O(n)；
# 4) 空间复杂度 O(1)，原地查找；
# 5) 对大规模均匀数据比二分查找更高效；
# 6) 若数据分布不均匀，效率可能下降。
# */

#
# 数据： [10, 20, 30, 40, 50, 60, 70]
# 查找 50 的位置: 4
# 查找 25 的位置: -1