本文作者:心月

插值查找算法介紹

心月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.eojird.tw/algorithm/142.html發布于 2019-07-01
文章轉載或復制請以超鏈接形式并注明出處心月IT博客

分享到:
贊(

發表評論

快捷輸入:

    評論列表 (有 0 條評論,人圍觀)參與討論