C/C++培训
达内IT学院
400-111-8989
C/C++培训
详细讲解C语言中插值查找法
插值查找其核心就在于插值的计算公式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++培训班，选达内就对了。
版权声明：转载文章来自公开网络，版权归作者本人所有，推送文章除非无法确认，我们都会注明作者和来源。如果出处有误或侵犯到原作者权益，请与我们联系删除或授权事宜。
预约申请免费试听课
填写下面表单即可预约申请免费试听！怕钱不够？可就业挣钱后再付学费！ 怕学不会？助教全程陪读，随时解惑！担心就业？一地学习，可全国推荐就业！
上一篇：详细讲解C语言中顺序查找法
-
扫码领取资料
回复关键字：视频资料
免费领取 达内课程视频学习资料
-
搜索抖音号搜索抖音号：1821685962
免费领取达内课程视频学习资料
Copyright © Tedu.cn All Rights Reserved 京ICP备08000853号-56 
京公网安备 11010802029508号 达内时代科技集团有限公司 版权所有
选择城市和中心
北京
黑龙江省
吉林省
内蒙古
河北省
陕西省
江苏省
湖北省
四川省
重庆
湖南省
江西省
贵州省
云南省
广西省
海南省
台湾