查找算法：插值查找算法实现及分析

川长思鸟来 2022-05-29 22:52 276阅读 0赞

# 插值查找算法介绍 #

**插值查找（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 = %d\n",index1,index2);
    	return 0;
    }

# 代码运行检测 #

![20180227201549966][]

[20180227201549966]: /images/20220530/a4090d2f3a994de9bd1534a354b4c65d.png