二分查找与二分答案（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 的数中，最小的数的指针。注意 lower_bound 是 “大于等于”，upper_bound 是 “大于”

标红的部分是 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 (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 即可