二分查找模板

缘起

二分查找是一个经常使用的模板, 见下

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
#include "stdafx.h"
#include <iostream>

#define LOCAL
#define N 10

using namespace std;

// 二分搜索 a[lo, hi) 中 target  注意, 使用二分搜索的前提是序列是单调的
int binsearch(int *a, int lo, int hi, int target)
{
	while (lo < hi)
	{
		int mi = (lo+hi)>>1;
		target<a[mi]?hi=mi:lo=mi+1;
	}
	return --lo; // 有多个命中元素时，总能保证返回秩最大者；查找失败时，能够返回失败的位置 循环结束时，lo为大于e的元素的最小秩，故lo - 1即不大于e的元素的最大秩
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int a[10];
	for(int i = 0; i <N; i++) scanf("%d", &a[i]);
	int ret = binsearch(a, 0, N, 4);
	cout<<ret << " "<<a[ret]<<endl;
	return 0;
}

注意，因为返回的是不大于 target的元素中的最大秩, 所以这个板子很方便的可以适用于 二分答案