插值查找
介绍
插值查找(Interpolation Search)是二分查找的一种改进版本,它借鉴了数值分析中的插值思想。跟二分查找的区别在于,插值查找会根据要查找的目标与查找区间的关系来动态确定下一次比较的位置,让查找点更靠近目标值。查找的数据分布比较均匀时,插值查找比二分查找更加高效。
算法步骤
- 确定查找范围的左边界 low 和右边界 high
- 根据查找值 key 与当前范围内的最小值和最大值的关系,计算出一个位置 pos:
pos = low + ((key - arr[low]) * (high - low)) / (arr[high] - arr[low])
- 将 arr[pos] 与 key 进行比较:
- 如果 arr[pos] = key,查找成功,返回 pos
- 如果 arr[pos] > key,在左半区间继续查找,high = pos - 1
- 如果 arr[pos] < key,在右半区间继续查找,low = pos + 1
- 重复步骤2-3,直到找到目标值或者 low > high(查找失败)

核心特性
- 改进的二分查找:根据目标值动态计算查找位置
- 要求有序:与二分查找一样,要求数据必须有序
- 时间复杂度:平均情况下为 O(log log n),最坏情况为 O(n)
...