插值查找

【概述】

以查字典为例，在英文字典中查 “apple” 时，下意识的会翻开前面的书页，当查 “zoo” 时，下意识的翻开一定是后面的书页，显然，此时还绝对不是从中间开始查起，而且有一定目的地从前或从后查找

同样的，以取值范围在 $1$ 到 $10000$ 间的从小到大均匀分布在数组中的 $100$ 个元素为例，若要查找元素 $5$，那么自然而然的会考虑从数组下标较小的开始查找

可以看出，对于二分查找这种查找方式，其并不是自适应的，因此，基于二分查找，就有了插值查找，其将查找点的选择改进为自适应选择，从而提高查找效率

简单来说，插值查找，就是根据要查找的关键字 $key$ 与查找表中最大最小记录的关键字比较后的查找方法，其核心在于插值的查找点的计算公式

【查找点的计算】

在二分查找中，查找点是中值，即：

$$mid=\frac{left+right}{2}$$

经过简单变换，有：

$$mid=left+\frac{1}{2}*(right-left)$$

而在插值查找中，对查找点的计算进行了一定的改进，即：

$$mid=left+\frac{key-a[left]}{a[right]-a[left]}*(right-left)$$

即将 $\frac{1}{2}$ 换为了能够自适应选择的插值点

$$\frac{key-a[left]}{a[right]-a[left]}$$

【时间复杂度】

从时间复杂度的角度来说，插值查找的最坏时间复杂度与二分查找相同，均为：

$$O(\log_2 n)$$

但对于表长较大，而关键字分布又比较均匀的查找表来说，其平均性能要比二分查找好的多

反之，若查找表中关键字分布非常不均匀，那么插值查找未必是很合适的选择

【实现】

int insertionSearch (int a[], int key, int left, int right) {
    int mid = low + (key - a[left]) / (a[right] - a[left]) * (right - left);
    if (a[mid] == value)
        return mid;
    else if (a[mid] > value)
        return insertionSearch(a, key, left, mid-1);
    else
        return insertionSearch(a, key, mid+1, right);
}