插值查找其核心就在于插值的计算公式key-arr[low]/arr[high]-arr[low]。细看是不是key在整序列中的占比哟。所以mid的计算公式为:(high-low)*(key-arr[low])/(arr[high]-arr[low])。对比折半查找的mid = (high-low)/2。

代码和折半查找一模一样，唯独mid的计算方式发生改变。

这样的好处在于，对表长较长，且关键字分分布比较均匀，插值查找算法的平均性能要比折半查找要好的多。但是 如果表中 关键字分布极端不均匀 那么插值查找还不如折半查找呢。

复杂度分析：O(log2(log2n))

#include<stdio.h>

//插值查找-C语言实现

//基本思路：二分查找改进版，只需改一行代码。

// mid=low+(key-a[low])/(a[high]-a[low])*(high-low)

int insertSearch(int *sortedSeq, int seqLength, int keyData);

int main()

{

int array[] = { 1, 2, 3, 4, 15, 26, 37, 78, 99 };

int location;

int target = 27; //待查找的数值

location = insertSearch(array, 9, target);

if(location != -1)

{

printf("已找到 位于 %d\n", location);

}

else

{

printf("找不到该数\n", location);

}

return 0;

}

int insertSearch(int *sortedSeq, int seqLength, int keyData)

{

int low = 0, mid, high = seqLength - 1;

while (low <= high)

{

mid = low + (high-low)*(keyData - sortedSeq[low]) / (sortedSeq[high] - sortedSeq[low]);

if (keyData < sortedSeq[mid])

{

high = mid - 1;//是mid-1，因为mid已经比较过了

}

else if (keyData > sortedSeq[mid])

{

low = mid + 1;

}

else

{

return mid;

}

}

return -1;

}

当你还在担心能否就业时，达内学员提前被企业录取;当你转辗于各大招聘会时，达内学员收到了高薪offer;当你在各大招聘网站投递简历时，达内学员中有人一毕业进入五百强名企。所以选择很重要。找C++培训班，选达内就对了。

版权声明：转载文章来自公开网络，版权归作者本人所有，推送文章除非无法确认，我们都会注明作者和来源。如果出处有误或侵犯到原作者权益，请与我们联系删除或授权事宜。