插值查找算法 原理与实现

在前面我们了解了二分查找，就是把一个集合的元素一分为二，用中间值和目标查找值相比较，直到要查找的值和中间值相等，则表示查找成功，反之表示不成功。为什么这里会再次提到二分查找呢？事实上，插值查找是二分查找的升级版。
用一个很简单的例子就可以把插值查找解释的很清楚。在字典里面找”boy”这个单词时，我们肯定不会从第一页开始找，而是从首字母为b的位置开始查找，然后再找到第二个字母在字母表中的位置，找到对应的位置后，重复这个过程，这样就可以快速的找到目标单词。
接下来就介绍一下插值查找吧。
我们知道的的二分查找有一个必要的前提，必须是有序的数组才可以进行二分查找，同样插值查找也只能用于一个呈线性增长的有序数组中。

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

在二分查找中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;
  }

最后

以上就是动听酸奶为你收集整理的插值查找算法 原理与实现的全部内容，希望文章能够帮你解决插值查找算法 原理与实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。