最近在论坛上看到的一种更简洁的办法

使用一个ans变量存储结果,这样就不用考虑那么复杂了,只要时刻清楚自己需要什么就可以了

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// 第一,求任意一个i使得array[i]等于val,不存在返回-1;
int BinarySearch1(vector<int> &array, int val){
int low = 0, high = (int)array.size() - 1, mid, ans = -1;
while(low <= high){
mid = (low + high)/2;
if(array[mid] <= val) {
low = mid + 1;
if(array[mid] == val) {
ans = mid;
break;
}
} else
high = mid - 1;
}
return ans;
}
// 第二,求最小的i使得array[i]等于val,不存在返回-1;
int BinarySearch2(vector<int> &array, int val){
int low = 0, high = (int)array.size() - 1, mid, ans = -1;
while(low <= high){
mid = (low + high)/2;
if(array[mid] < val){
low = mid + 1;
}
else{
high = mid - 1;
if(array[mid] == val){
ans = mid;
}
}
}
return ans;
}
// 第三,求最大的i使得array[i]等于val,不存在返回-1;
int BinarySearch3(vector<int> &array, int val){
int low = 0, high = (int)array.size() - 1, mid, ans = -1;
while(low <= high){
mid = (low + high)/2;
if(array[mid] <= val){
low = mid + 1;
if(array[mid] == val){
ans = mid;
}
} else
high = mid - 1;
}
return ans;
}
// 第四,求最大的i使得array[i]小于val,不存在返回-1;
int BinarySearch4(vector<int> &array, int val){
int low = 0, high = (int)array.size() - 1, mid, ans = -1;
while(low <= high){
mid = (low + high)/2;
if(array[mid] < val){
low = mid + 1;
ans = mid;
}
else
high = mid - 1;
}
return ans;
}
// 第五,求最小的i使得array[i]大于val,不存在返回-1;
int BinarySearch5(vector<int> &array, int val){
int low = 0, high = (int)array.size() - 1, mid, ans = -1;
while(low <= high){
mid = (low + high)/2;
if(array[mid] <= val){
low = mid + 1;
}
else{
high = mid - 1;
ans = mid;
}
}
return ans;
}

newly add at 2015/11/26

如果需要查找比如大于某个数的最小的数时,我们有时候会迷惑,其实我们可以从最后查找出来的结果来看。

我们假如要在一个数组3, 6, 7, 9中查找大于5的最小的数,我们最后通过上下界的方法查找出来的结果应该是3, 6,其中上界所指向的位置就是我们所需要查找的值。没有第二种可能说我们最后查找出来的结果是6, 7,这是不存在的。

最后考虑到两种极端情况,比如说查找比1大的最小的数,和比10大的最小的数,这两种情况就决定了我们上下界的初始取值,lb = -1, ub = size;

这样就可以很好地解决二分查找的问题,不用去背什么情况下上界该取什么值,下界该取什么值,中间的状态如何变化。


我们可以很快地写出在已排序数组中查找某一个数的代码,但是如果我们要找出某个数的上界和下届有时候就会多费点心思,在这里我们可以看看这三种方式的不同之处,另外,在实际应用中,我们可以不用自己是实现,直接使用STL中的upper_bound和lower_bound函数就可以了。

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
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <vector>
using namespace std;
//精确查找某一个值
//如果有的话,返回第一个找到的值
//如果没有的话,返回-1
int binarySearch(vector<int> &A, int x) {
int size = (int)A.size();
int lb = 0, ub = size - 1;
while (lb <= ub) {
int mb = lb + (ub - lb)/2;
if (A[mb] == x)
return mb;
else if (A[mb] > x)
ub = mb - 1;
else
lb = mb + 1;
}
return -1;
}
//在数组中查找x的上界,即小于等于x的最大值
//如果有,返回上界
//如果没有,返回-1
int upperBound(vector<int> &A, int x) {
int size = (int)A.size();
int lb = -1, ub = size;
while (ub - lb > 1) {
int md = lb + (ub - lb) / 2;
//如果满足条件,那么符合条件的范围就是[mid,ub)
if (A[md] <= x)
lb = md;
else
ub = md;
}
return lb;
}
//在数组中查找x的下界,即大于等于x的最小值
//如果有,返回下界
//如果没有,返回n
int lowerBound(vector<int> &A, int x) {
int size = (int)A.size();
int lb = -1, ub = size;
while (ub - lb > 1) {
int md = lb + (ub - lb) / 2;
//如果满足条件,那么符合条件的范围就是(mid, ub]
if (A[md] >= x)
ub = md;
else
lb = md;
}
return ub;
}
//10 10 10 20 20 20 30 30
int main() {
int myints[] = {10,20,30,30,20,10,10,20};
vector<int> test(myints, myints + 8);
sort(test.begin(), test.end());
cout<<binarySearch(test, 15)<<endl;
cout<<upperBound(test, 38)<<endl;
cout<<lowerBound(test, 5)<<endl;
}