本文作者:心月

插值查找算法介绍

心月IT博客 2019-02-26
摘要:插值查找(Interpolation Search)是根据要查找关键字key与查找表中最大最小记录的关键字比较后的查找方法,其核心就在于插值的计算公式key-arr[low] arr[high]-arr[low]。细看是不是key在整序列中的占比哟。

插值查找(Interpolation Search)是根据要查找关键字key与查找表中最大最小记录的关键字比较后的查找方法,其核心就在于插值的计算公式key-arr[low]/arr[high]-arr[low]细看是不是key在整序列中的占比哟。所以mid的计算公式为:

(high-low)*(key-arr[low])/(arr[high]-arr[low])。对比折半查找的mid = (high-low)/2

代码和折半查找一模一样,唯独mid的计算方式发生改变。这样的好处在于,对表长较长,且关键字分分布比较均匀,插值查找算法的平均性能要比折半查找要好的多。但是 如果表中 关键字分布极端不均匀 那么插值查找还不如折半查找呢

插值查找算法代码

  1.  
    #define _CRT_SECURE_NO_WARNINGS
  2.  
    #include <stdio.h>
  3.  
    //插值查找法 arr数组,length 数组长度,key 查找的关键字
  4.  
    //返回查找值的下标 ,没查找到 返回-1
  5.  
    int Interpolation_Search(int *arr, int length, int key)
  6.  
    {
  7.  
    int low = 0;//低位下标
  8.  
    int high = length-1;//高位下标
  9.  
    int mid;//中间值下标
  10.  
    while (low <= high)
  11.  
    {
  12.  
    mid = (high-low)*(key - arr[low]) / (arr[high] - arr[low]);//插值
  13.  
    if (key < arr[mid])
  14.  
    {
  15.  
    high = mid - 1;
  16.  
    }
  17.  
    else if(key > arr[mid])
  18.  
    {
  19.  
    low = mid + 1;
  20.  
    }
  21.  
    else
  22.  
    {
  23.  
    return mid;
  24.  
    }
  25.  
    }
  26.  
    return -1;
  27.  
    }
  28.  
    int main(int argc, char *argv[])
  29.  
    {
  30.  
    int arr[10] = { 0,1,2,3,4,5,6,7,8,9};
  31.  
    int index1 = Interpolation_Search(arr, 10, 5);
  32.  
    int index2 = Interpolation_Search(arr, 10, 100);
  33.  
    printf("index1 = %d,index2 = %dn",index1,index2);
  34.  
    return 0;
  35.  
    }
 

代码运行检测

 

文章版权及转载声明:

作者:心月 本文地址:http://www.xinyueseo.com/algorithm/142.html发布于 2019-09-07
文章转载或复制请以超链接形式并注明出处心月IT博客

分享到:
赞(

发表评论

快捷输入:

    评论列表 (有 0 条评论,人围观)参与讨论