二分查找与二分答案（2）
溢出风险
我们首先回顾一下上一次二分算法的代码
#include<iostream>
using namespace std;
int n,x,a[1000000];
int binary_search(int a[],int n,int x)
{
int l = 0;
int r = n - 1;
int ans = -1;
while(l <= r)
{
int m = (l + r) / 2;
if(a[m] == x)
{
ans = m;
break;
}
if(a[m] < x)
l = m + 1;
else
r = m - 1;
}
return ans;
}
int main()
{
cin >> n >> x;
for(int i = 0;i < n;i++)
cin >> a[i];
int ans = binary_search(a,n,x);
cout << ans;
return 0;
}之所以重新把代码拿出来，肯定是因为有不妥之处，我们看一下第11行m=(l+r)/2 假如l=1999999998，r=1999999999，虽然l和r都没有超出int的范围，但是计算m时，l+r就超过int范围了，导致m计算错误，整个算法挂掉 解决办法很简单，改成m=l+(r-l)/2，这样就不会有溢出的风险了
其他问题
我们解决了最简单的二分查找问题：a数组单调递增，并且其中没有重复的数值。我们遇到的实际问题可能就没有这么简单，可能会有重复的数值。比如a数组里有3个5。这时我们查找5就有一个问题：到底返回哪一个5的下标？ 此外，在之前的简单版本中，如果查找的x不在数组中，我们就返回-1。但是实际的问题中，即便x不在数组中，我们可能需要知道与x大小接近的数值在数组中处于什么位置。不能只返回一个-1了事。 为了解决这些问题，C++STL提供了两个特别好用的函数：lower_bound()和upper_bound()
lower_bound()
假设有一个a数组，数组长度是n，lower_bound(a,a+n,x)返回数组a[0]~a[n-1]，大于等于x的数中，最小的数的指针。由于指针可以通过加减算偏移量，所以我们再减去a(数组名会被隐式转换成指针)，就得到了相应的下标。下面给个例子，假设我们在a数组中找3这个数。
左边是a数组，当然这个a数组必须递增的，不然lower_bound()会出错。其中标红的是大于等于3的数。右边是lower_bound()的返回值减去a，是标红这些数里最小的一个的下标。注意最后一个例子，如果a数组中一个大于等于3的都没有，会返回数组长度n。
upper_bound()
同样假设a是一个数组，n是数组长度，upper_bound(a, a+n, x)返回数组a[0]~a[n-1]中，大于x的数中，最小的数的指针。<font color = red>注意lower_bound是“大于等于”，upper_bound是“大于”。</font>
标红的部分是a数组中大于3的数。upper_bound的返回值减去a是这些数里最小的一个的下标。 其实对于lower_bound和upper_bound还有一个等价的解释。就是假设我要在a数组中插入x，然后还保持递增，那么lower_bound返回的是x最小的可以插入的数组位置，upper_bound返回的是x最大的可以插入的数组位置。
可以参考上面的图，当然lower_bound和upper_bound并不是真的返回2和5，返回的是指针，减去a之后才是2和5 我们通过一个程序看一下lower_bound和upper_bound的用法
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int a[10] = {1,2,2,3,3,3,4,4,4,4};
int n = 10;
for(int i = 0;i <= 5;i++)
{
int *lower = lower_bound(a,a + n,i);//循环查找最小大于等于i的指针
int *upper = upper_bound(a,a + n,i);//循环查找最小大于i的指针
cout << lower - a << " " << upper - a << endl;
}
return 0;
}
/*
0 0
0 1
1 3
3 6
6 10
10 10
*/另外lower_bound和upper_bound的前两个参数是其实是待查范围的首尾指针(左闭右开区间，不包括尾指针)，所以也可以写别的参数。比如下面的程序就是从a[1]开始查找：
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int a[10] = {1,2,2,3,3,3,4,4,4,4};
int n = 10;
for(int i = 0;i <= 5;i++)
{
int *lower = lower_bound(a + 1,a + n,i);//循环查找最小大于等于i的指针
int *upper = upper_bound(a + 1,a + n,i);//循环查找最小大于i的指针
cout << lower - a << " " << upper - a << endl;
}
return 0;
}
/*
0 0
0 1
1 3
3 6
6 10
10 10
*/lower_bound和upper_bound除了能用在数组上，还可以用在vector上。我们知道vector就相当于一个可以长度可变的数组。当用于vector上时，需要注意前两个参数必须是vector的迭代器，同时函数的返回值也是迭代器：
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int a[10] = {1,2,2,3,3,3,4,4,4,4};
vector<int> b(a,a + 10);
int n = 10;
for(int i = 0;i <= 5;i++)
{
vector<int>::iterator lower = lower_bound(b.begin(),b.end(),i);//循环查找最小大于等于i的指针
vector<int>::iterator upper = upper_bound(b.begin(),b.end(),i);//循环查找最小大于i的指针
cout << lower - b.begin() << " " << upper - b.begin() << endl;
}
return 0;
}
/*
0 0
0 1
1 3
3 6
6 10
10 10
*/自定义lower_bound()和upper_bound()函数
- my_lower_bound()函数
首先函数my_lower_bound(int a[],int n,int x)的参数分别是数组a，数组a的长度，带查找的元素x，而这个函数的实现，其实稍微改一下我们之前的二分查找代码即可
#include<iostream>
using namespace std;
int n,x,a[1000000];
int my_lower_bound(int a[],int n,int x)
{
int l = 0;
int r = n - 1;
int ans = n;
while(l <= r)
{
int m = l + (r - l) / 2;
if(a[m] >= x)
{
ans = m;
r = m - 1;
}
else
r = m + 1;
}
return ans;
}
int main()
{
cin >> n >> x;
for(int i = 0;i < n;i++)
cin >> a[i];
int lower = my_lower_bound(a,n,x);
cout << lower;
return 0;
}关键代码从第12行开始。如果中间的这个数a[m]是大于等于x的。记得我们要找的是”大于等于x的数中最小的数的下标“。现在我们发现了一个大于等于x的数a[m]，当前这个下标m是我们已知最小的，所以就在第13行把m的值赋值给答案ans。然后因为我们已经知道a[m]是一个“大于等于x的数”，所以a[m+1], a[m+2]…a[r]都不用再考虑了。只需要在a[l]~a[m-1]中查找是不是还有大于等于x的数”，于是第15行我们令r = m – 1。 如果a[m]<x，那a[l], a[l+1], … a[m]一定都小于x，都不满足”大于等于x”这个条件。所以我们只需要在a[m+1], a[m+2], … a[r]中再查找x。于是第18行我们令l = m + 1 my_upper_bound()的函数我就不写了，upper_bound是找“大于x的数中，最小数的下标”，而lower_bound是找“大于等于x的数中，最小数的下标”，所以对于my_upper_bound函数，我们只要把上面代码中第12行的“a[m]>=x”改成“a[m]>x”即可