![](https://csdnimg.cn/release/download_crawler_static/10556830/bg8.jpg)
8
注:折半查找的前提条件是需要有序表顺序存储,对于静态查找表,一次排序后不再变化,
折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说,维护有
序的排序会带来不小的工作量,那就不建议使用。——《大话数据结构》
#include<stdio.h>
//二分查找-C 语言实现
//基本思路:将排序好的数据存放到数组里(不能是链表)
// 这只前中后标签,与中间元素比,若小于就将后变为原来的中
// 继续计算中,比较,循环,直至等于中,或循环结束。
int binsearch(int *sortedSeq, int seqLength, int keyData);
int main()
{
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int location;
int target = 4;
location = binsearch(array, 9, target);
printf("%d\n", location);
return 0;
}
int binsearch(int *sortedSeq, int seqLength, int keyData){
int low = 0, mid, high = seqLength - 1;
while (low <= high){
mid = (low + high) / 2;//奇数,无论奇偶,有个值就行
if (keyData < sortedSeq[mid]){
high = mid - 1;//是 mid-1,因为 mid 已经比较过了
}else if (keyData > sortedSeq[mid]){
low = mid + 1;
}else{
return mid;
}
}
return -1;
}
3、插值查找
在介绍插值查找之前,首先考虑一个新问题,为什么上述算法一定要是折半,而不是折四分
之一或者折更多呢?
打个比方,在英文字典里面查“apple”,你下意识翻开字典是翻前面的书页还是后面的书
页呢?如果再让你查“zoo”,你又怎么查?很显然,这里你绝对不会是从中间开始查起,
而是有一定目的的往前或往后翻。
同样的,比如要在取值范围 1 ~ 10000 之间 100 个元素从小到大均匀分布的数组中查找 5,
我们自然会考虑从数组下标较小的开始查找。