折半查找的分析与实现

发表于 | 分类于
字数统计: 659 word | 阅读时长 ≈ 2 min
折半查找

折半查找又称二分查找，它是一种效率较高的查找方法。但是折半查找要求查找序列中的元素是有序的，为了简单，假设序列是递增有序的。
折半查找的基本思路：设 a[low···high] 是当前的查找区间，首先确定该区间的中点位置mid=(low+high)/2 (取下界);然后将待查的 k值 与 a[mid].key 比较：

（1）若k==a[mid].key,则查找成功并返回该元素的物理下标
（2）若k<a[mid],则由表的有序性可知 a[mid···high] 均大于k，因此表中若存在值
等于k的元素，则该元素必定位于 左子表 a[low···mid-1] 中，故新的查找区间
是左子表a[low···mid-1]。
（3）若k>a[mid],则要查找的元素必定位于 右子表 a[mid+1···high] 中，故新的查找区间
是右子表a[mid+1···high]。
下一次查找是针对新的查找区间进行的。
因此可以从最初的查找区间a[0···n-1]开始，每经过一次与当前查找区间中点位置上的关键字比较就可以确定查找是否成功，不成功则当前的查找区间缩小一半。重复这一过程，直到找到关键字为K的元素，或者直到当前的查找区间为空（即查找失败）时为止。

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 #include<iostream>
using namespace std;
//折半查找
int BinSearch(int a[], int low, int high, int k){
	int mid;
	if (low <= high){			//当前区间存在元素时
		mid = (low + high) / 2;	//求查找区间的中间位置
		if (a[mid] == k){		//找到了，直接返回其物理下标 mid
			return mid;
		}
		if (a[mid] > k){		//当a[mid]>k 时在a[low···mid-1]中递归查找
			return BinSearch(a, low, mid - 1, k);
		}
		else{					//当a[mid]<k 时在a[mid+1···high]中递归查找
			return BinSearch(a, mid + 1, high, k);
		}
	}
	else{
		return -1;				//找不到，错误处理
	}
}
int main(){
	int n = 10, i;
	int k = 6;				    //要找的值
	int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	i = BinSearch(a, 0, n - 1, k);
	if (i >= 0){
		cout << "第" << i << "个元素值为k";
	}
	return 0;
}
附：(非递归实现)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int BinSearch(int a[], int n, int k){  //在含有n个元素的数组a中查找 是否有值为K的元素
	int low = 0, high = n - 1, mid;
	while (low <= high){
		mid = (low + high) / 2;
		if (a[mid] == k){
			return mid;
		}
		if (a[mid] > k){
			high = mid - 1;
		}
		else{
			low = mid + 1;
		}
	}
	return -1;
}
0%