插值查找

回顾二分查找：

1. 数组已经排好序
2. 每次查找范围缩小一半

插值查找仍然要求是 有序的数组，优化主要是优化在寻找 mid 上面。

思考🤔：为什么每次要折半而不是折四分之一或者更多呢 ？

• apple：翻开书的靠前的部分
• zoo：翻开书的靠后的部分

插值查找的核心思想就是通过 估算目标元素的位置 来进行查找，而不是简单地将查找范围分为两部分。

公式推导#

假设我们用 mid 来表示目标值的位置，我们的目标是根据目标值与区间端点的关系，推算出一个 mid：

1. 比例关系：目标值 target 位于区间 [arr[low], arr[high]] 内。我们可以用 target 与 arr[low] 和 arr[high] 的相对位置来估算 mid。
   • target 与 arr[low] 的差是 target - arr[low]。
   • arr[high] 与 arr[low] 的差是 arr[high] - arr[low]。
2. 目标值位置的比例：target 距离 arr[low] 的距离与 arr[low] 到 arr[high] 的距离之间的比例可以表示为：

​ 这个比例表示 target 在整个区间中的相对位置。

3. 估算中间位置：根据这个比例，target 在整个区间中的位置应该与 arr[low] 和 arr[high] 之间的距离成比例。因此，我们可以估算 mid 的位置为：

这个公式表示，mid 是在 low 和 high 之间的一个估算位置，考虑了目标值 target 在区间内的相对位置。

换句话说，现在我们的 mid 是根据比例计算出来的，而非简单的折半。

具体示例#

假设数组是 [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]，要查找目标值 70。

1. low = 0，high = 9，arr[low] = 10，arr[high] = 100，target = 70。

2. 使用插值公式计算 mid：

   $$\text{mid} = 0 + \left( \frac{70 - 10}{100 - 10} \right) \times (9 - 0) = 0 + \left( \frac{60}{90} \right) \times 9 = 0 + 0.6667 \times 9 = 6$$

   计算得到 mid = 6，然后比较 arr[mid] = 70，恰好等于目标值，因此查找成功。

可以看到，通过这种方式，能够直接 估算出一个合理的位置，减少了不必要的查找步骤。

插值查找其实也有一个隐式的条件，就是数据尽量是 分布均匀 的数据。

注意点#

插值查找的数据集必须是均匀分布的，这样算出来的比例才是有意义的。

如果是非常不均匀的数据，差值查找的效率可能不如预期，因为计算出来的比例有问题。例如，在一个大量小值和极少数大值的数组中，插值查找可能会把 mid 估算到靠近数据尾部的地方，而目标值却可能位于前半部分，这样每次估算都会出现不必要的偏差。

例如一个数组 [1, 2, 3, 4, 5, ... 99, 100, 9000, 10000]，如果你在这个数组中搜索一个值，比如 9000，插值查找可能会低估目标值的位置，因为 9000 与前面的小值差距太大。我们代入到公式去计算一下：

首先计算比例：

然后计算 mid：

由于 mid 必须是整数，通常会向下取整（如果是浮动值），所以得到 mid = 90。

可以看到，此时插值查找的效率就会变差，需要多次迭代才能找到目标值，时间复杂度可能退化到线性查找 O(n) 的时间复杂度。

代码实现#

function search(arr, target) {
  // 基本上和二分查找非常相似，区别就是找 mid 值的地方已经跳出 while 循环的条件
  let low = 0 // 起始下标
  let high = arr.length - 1 // 末尾下标

  while (low <= high && target >= arr[low] && target <= arr[high]) {
    // 计算mid，不再是一分为二，而是计算比例
    // 比例的计算根据公式来算
    let mid =
      low +
      Math.floor(((target - arr[low]) * (high - low)) / (arr[high] - arr[low]))

    // 后面就和二分查找的逻辑一模一样
    if (arr[mid] === target) {
      return mid
    } else if (arr[mid] > target) {
      high = mid - 1
    } else {
      low = mid + 1
    }
  }
  return -1
}

const arr = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
const target = 70
const result = search(arr, target)
console.log(result)

const target2 = 85
const result2 = search(arr, target2)
console.log(result2)

总结：

1. 整个插值查找和二分查找的逻辑基本一致，唯一的区别就是对于 mid 的计算。
2. 跳出循环的条件，需要新增加对于越界问题的防护，因为计算出来的 mid 可能不在数组的有效范围内。

-EOF-