插值查找类似二分法查找。插值查找的前提是数列是有序的，假定这个有序数列是关于序号的直线，如图9-1所示，数组的下标为坐标值，有序数列的系列值构成关于该坐标的直线。

图9-1 插值查找

根据图中三角形的比例关系，预估要查找的元素的位置。假设图中pos为预估值的位置，a[pos]为预估值，所以有

预估待查找数据的可能位置为

计算待查找数据可能的位置pos后，将待查数据与pos位置上的数值a[pos]进行比较，如果该值与待查找的数据相同，则查找成功；否则，继续判断待查找数据的范围。如果待查找的数小于a[pos]，则待查找数在左边low～pos-1区间，重新设定high=pos-1作为右边界；反之，待查数据在pos-1～high区间，重新设定low=pos+1作为左边界，继续进行查找。就这样一直缩小范围来确定最终的目标

待查数据的分布越接近线性，插值查找方法的效率就越高。

【例9-17】有序数组的插值查找程序。(www.daowen.com)

程序思路：根据图9-1，假设待查数据value的位置为pos，确定待查数据所在区间内，通过不断缩小查找区间low～high，来进行查找。

程序运行结果：

5

【例9-18】使用递归算法的插值查找程序。

程序思路：使用递归方法进行插值查找时，先设定序列的左右边界low与high，对以low和high作为边界的子序列进行查找，然后根据待查值所在的区间重新设定边界，缩小规模，进行递归。递归的出口有两个，一个是查找到数值；另一个出口为查找失败。查找失败的条件有左右边界重合、左右边界的值相同、要查找的值小于左边界或大于右边界。

程序运行结果：

5