折半查找法

折半查找法

折半查找法，一种基于分治思想的查找算法，对于一串按照从小到大或从大到小顺序排列的数字，折半查找法最坏的时间复杂度为O(logn)。竞赛题中考察的折半，往往需要自行确定边界值。而边界值的确定往往需要借助复杂的数学公式，或者需要手动编写模拟代码确定大致的边界值，随后再通过折半查找法求解。

递归折半

查看代码 
#include 
using namespace std;
int a[10001], key;
void search(int l, int r) {
	int mid;
	if (r>=l) {
		mid = (r+l)/2;
		if (key==a[mid]) {
			printf("%d", mid);
			return ;
		}
		else if (key

非递归折半

查看代码 
#include 
using namespace std;
int n, a[10001], key;
void search() {
	int l = 1, r = n;
	while (l<=r) {
		int mid = (l+r)/2;
		if (key==a[mid]) {
			printf("%d", mid);
			return ;
		} else if (keya[n]) puts("-1");
	else search();
	return 0;
}
算法系列笔记

相关

标签