介绍

插值查找，它是二分查找的变种，它只适用于有序递增系列。其时间复杂度 O (log2n) 。

插值查找算法只适用于有序序列，换句话说，它只能在升序序列或者降序序列中查找目标元素。作为 “改进版” 的二分查找算法，当有序序列中的元素呈现均匀分布时，插值查找算法的查找效率要优于二分查找算法；反之，如果有序序列不满足均匀分布的特征，插值查找算法的查找效率不如二分查找算法。

所谓均匀分布，是指序列中各个相邻元素的差值近似相等。例如，{10, 20, 30, 40, 50} 就是一个均匀分布的升序序列，各个相邻元素的差值为 10。再比如 {100, 500, 2000, 5000} 是一个升序序列，但各相邻元素之间的差值相差巨大，不具备均匀分布的特征。

插值查找改变了二分查找中原有的中值 mid 的求解方式，其 mid 不再代表中值，而是使用了一个插值公式：

$$mid=l e f t+\frac{(x-V a l[l e f t]) \times(\text { right }-l e f t)}{V a l[r i g h t]-V a l[l e f t]} ​$$

式子中，各部分的含义分别是：

• $mid$：计算得出的元素的位置；
• $right$：搜索区域内最后一个元素所在的位置；
• $left$：搜索区域内第一个元素所在的位置；
• $x$：要查找的目标元素；
• $Val[]$：表示整个待搜索序列。

实现

JavaScript

/**
 * Interpolation Search
 *
 * Time Complexity:
 * -Best case: O(1)
 * -Worst case: O(n)
 * -O((log(log(n))) If the data are uniformly distributed
 */

function interpolationSearch (arr, key) {
  const length = arr.length - 1
  let low = 0
  let high = length
  let position = -1
  let delta = -1

  // Because the array is sorted the key must be between low and high
  while (low <= high && key >= arr[low] && key <= arr[high]) {
    delta = (key - arr[low]) / (arr[high] - arr[low])
    position = low + Math.floor((high - low) * delta)

    // Target found return its position
    if (arr[position] === key) {
      return position
    }

    // If the key is larger then it is in the upper part of the array
    if (arr[position] < key) {
      low = position + 1
      // If the key is smaller then it is in the lower part of the array
    } else {
      high = position - 1
    }
  }

  return -1
}