本文作者:心月

插值查找算法介绍

心月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的计算方式发生改变。这样的好处在于,对表长较长,且关键字分分布比较均匀,插值查找算法的平均性能要比折半查找要好的多。但是 如果表中 关键字分布极端不均匀 那么插值查找还不如折半查找呢

插值查找算法代码

  #define _CRT_SECURE_NO_WARNINGS
 
#include <stdio.h>
 
//插值查找法 arr数组,length 数组长度,key 查找的关键字
 
//返回查找值的下标 ,没查找到 返回-1
 
int Interpolation_Search(int *arr, int length, int key)
 
{
 
int low = 0;//低位下标
 
int high = length-1;//高位下标
 
int mid;//中间值下标
 
while (low <= high)
 
{
 
mid = (high-low)*(key - arr[low]) / (arr[high] - arr[low]);//插值
 
if (key < arr[mid])
 
{
 
high = mid - 1;
 
}
 
else if(key > arr[mid])
 
{
 
low = mid + 1;
 
}
 
else
 
{
 
return mid;
 
}
 
}
 
return -1;
 
}
 
int main(int argc, char *argv[])
 
{
 
int arr[10] = { 0,1,2,3,4,5,6,7,8,9};
 
int index1 = Interpolation_Search(arr, 10, 5);
 
int index2 = Interpolation_Search(arr, 10, 100);
 
printf("index1 = %d,index2 = %dn",index1,index2);
 
return 0;
 
}

代码运行检测

代码运行检测

 

文章版权及转载声明:

本文由:IT技术博客 心月整理分享于 2019-11-18 20:17:08
若转载请注明原文及出处:http://www.xinyueseo.com/algorithm/142.html

分享到:
赞(
发表评论
快捷输入:

验证码

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