首页 > 代码库 > 什么是差值查找?
什么是差值查找?
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 <stdio.h> #include <stdlib.h>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; else return 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); else printf("未在数组中找到元素:%d\n", key); system("pause"); return 0;}
什么是差值查找?