什么是差值查找?

1.插值查找与二分查找很类似,都是用于在有序的基础上查找某个元素

2.二分查找的原理是,每次都取一半,然后与mid值比较,再决定下一次查找的范围

3.设想在一本英文字典里查找某个单词,因为是根据字母序排列好的,你不会傻到采用二分查找的方法,先找到这本字典的一半,再取这本字典的四分之一...这样下去比较吧,这种效率显然不是最快的,此时就轮到我们的差值查找出场了.

4.差值公式的推导:

有序序列: 1 2,3,4,5,6,7,8,9,10

比例公式:   假设数组a[i]已经有序

(key-low)/a[key]-a[low] =(high-low)/a[high]-a[low];

key-low=(high-low) *(a[key]-a[low])/a[high]-a[low];

key =low +(high-low) *(a[key]-a[low])/a[high]-a[low];

将key替换为mid,即第key个位置,此时是需要比较的位置,是mid,a[key]替换为key,要查找的值,即我们要查找位置为mid上的是否等于key

mid =low +(high-low) *(key-a[low])/a[high]-a[low];

5.差值查找需要满足的两个条件:

 a.每一次对数据的访问与通常的指令相比，费用都是相当昂贵的。例如，待查找的表一定是在磁盘而非内存中，因而每一次比较都要进行磁盘访问。此时查找查找的效率优势就可以明显体现出来

b.  数据表有序,且均匀分布,如电话簿,字典即是均匀分布的.例如{1 2,3,4,5,6,7,8,9,10}是均匀分布,而{1,3,7,11,16,21,27...}就不是均匀分布的.此时使用差值查找和二分查找比较的话,优势体现不明显.

代码如下:

#define  _CRT_SECURE_NO_WARNINGS#include  
#include 
int Bin_Search(int *a, int key, int n)
{int low, high, mid;low = 0;high = n - 1;while (low <= high){mid = low + (high - low) * (key - a[low]) / (a[high] - a[low]); //此处于二分查找不同,套用插值公式  if (a[mid] > key)         //如果key比插值小,把高位调整为插值下标的下一位            high = mid - 1;else if (a[mid] < key)low = mid + 1;elsereturn mid;}return -1;
}
int mainA()
{int a[] = { 1, 5, 17, 25, 33, 38, 46, 55, 69, 75, 99 };int key;int len = sizeof(a) / sizeof(*a);printf("请输入要查找的值:\n");scanf("%d", &key);int pos = Bin_Search(a, key, len);if (pos != -1)printf("在数组的第%d个位置找到:%d\n", pos + 1, key);elseprintf("未在数组中找到元素:%d\n", key);system("pause");return 0;
}

转载于:https://www.cnblogs.com/ttss/p/4069649.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！