物联网
您现在所在的位置:首页>企业动态>物联网

插值查找

编辑:学到牛牛IT培训    发布日期: 2022-03-10 14:06:16  

在前面我们了解了二分查找,就是把一个集合的元素一分为二,用中间值和目标查找值相比较,直到要查找的值和中间值相等,则表示查找成功,反之表示不成功。为什么这里会再次提到二分查找呢?事实上,插值查找是二分查找的升级版。

用一个很简单的例子就可以把插值查找解释的很清楚。在字典里面找”boy”这个单词时,我们肯定不会从第一页开始找,而是从首字母为b的位置开始查找,然后再找到第二个字母在字母表中的位置,找到对应的位置后,重复这个过程,这样就可以快速的找到目标单词。

接下来就介绍一下插值查找吧。

我们知道的的二分查找有一个必要的前提,必须是有序的数组才可以进行二分查找,同样插值查找也只能用于一个呈线性增长的有序数组中。

图片2.png


首先我们在数组中找到左边索引low和右边的索引high,目标查找值key

图片3.png

在二分查找中mid表示数组的中间值,而插值查找中mid表示一个自适应处,插值查找每次是从自适应mid处开始查找,mid的计算方式为:low + (key – arr[low]) / (arr[high] – arr[low]) * (high - low);在这里mid表示的就是目标值key在序列总的所占比。

源码:

int func(int arr[], int len, int key)

{

       int low,high,mid;

       low = 0;

       high = len-1;

   int h = (key-arr[low])/(arr[high]-arr[low]);

       while(low <= high)

      {

          mid = h * (high - low);

          if(key < arr[mid])

          {

              high = mid - 1;

          }

          else if(key > arr[mid])

          {

             low = mid + 1;

          }

          else

          {

              return mid;

          }

      }

     return -1;

  }


免费试学
课程好不好,不如实地听一听

封闭学习

2

1

联系我们

电话:028-61775817

邮箱:1572396657@qq.com

地址:成都高新西区西芯大道4号

  • 学到牛牛在线咨询

    扫一扫,免费咨询

  • 学到牛牛公众号

    微信公众号

学一流技术,找高薪工作

7-24小时服务热线:

028-61775817

版权声明 网站地图

蜀ICP备2021001672号

课程问题轻松问