二分法介绍

二分法最简单的用法是在一个有序序列中查找一个数x,每次选择中间数进行猜测,不断的缩小其范围。这是最基本的办法,但是二分法的用处不止如此,比如我们直到一个序列的规律之后,我们可以利用某些条件,来逼近我们想要的结果。

下面是代码:

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
    

*/

int (int a[], int left, int right, int x) {
int mid;
while(left <= right) {//当等于的时候也要判断一下,a[mid] == x
mid = left + (right + left) / 2;//避免yi'ch4u
if(a[mid] == x) {
return mid;
}else if(a[mid] > x) {
left = mid + 1;
}else{
right = mid - 1;
}
}
return -1;
}

/**
* 求出序列中第一个大于等于X的位置,以及第一个大于x的位置,这个位置是假设存在的应该的值
*/

//求出序列中第一个大于等于X的位置
int lower_bound(int a[], int left, int right, int x) {
//用left与right不断的逼近,最小的大于x的点
int mid;
while(left < right) {//等于的时候说明找到了唯一的点
mid = left + (right - left) / 2;
if(a[mid] >= x) {
right = mid;
}else{
left = mid + 1;
}
}
return left;
}
//求出序列第一个大于x元素的位置
int upper_bound(int a[], int left, int right, int x) {
int mid;
while(left < right) {
mid = left + (right - left) / 2;
if(a[mid] > x) {
right = mid;
}else{
left = mid + 1;
}
}
return left;
}

/**
* 总结:以上的代码说明了同一个问题,在有序的序列中寻找第一个满足条件的位置,基本思想是找到满足条件的位置,
* 然后不断缩小位置,直到找到了唯一解:left = right, 而如果只查询是否存在用第一种解法。
*/