二分查找与二分答案详解

2.2.while(l<=r)

尽量向左找目标

//在 a 数组中寻找第一个>=x 的数，并返回其下标
int bsearch_1(int l, int r) {
    int res = 0x3f3f3f3f; //可以先将 res 设置为一个很大的数，如果 while 循环终止后 res 没变，便没找到
    while (l <= r) {
        int mid = l + r >> 1; //或写成 (l+r)/2
        if (a[mid] >= x) {
            r = mid - 1;
            res = mid;
        } else {
            l = mid + 1;
        }
    }
    return res;
}

尽量向右找目标

//在 a 数组中寻找最后一个<=x 的数，并返回其下标
int bsearch_2(int l, int r) {
    int res = 0x3f3f3f3f; //可以先将 res 设置为一个很大的数，如果 while 循环终止后 res 没变，便没找到
    while (l <= r) {
        int mid = l + r >> 1; //或写成 (l+r)/2
        if (a[mid] <= x) {
            l = mid + 1;
            res = mid;
        } else {
            r = mid - 1;
        }
    }
    return res;
}

2.3.代码细节解析

首先，区间是有单调性的，我们想查找目标值第一次出现的位置，如果查到一个值比目标值大，就把右半边丢掉，因为右半边肯定也比目标值大；同样，如果查到值比目标值小，那就丢掉左半边。

1. l+r>>1 什么意思？ 这个是位运算写法，将整数类型的二进制表示右移一位，等同于 (l+r)/2，注意，double 类型不适用这一点。

2. 循环条件 l<=r 和 l<r 有什么区别？ 本质上没什么区别，只是循环终止条件不同，个人建议用 l<r，代码简便，清晰明了。

3. 为什么当循环条件为 l<=r 时要用 res 来记录答案，为 l<r 时直接返回 l 或 r 即可？ 因为当循环条件为 l<r 时，在循环的过程中，可以发现当 mid 满足条件时 l 和 r 的更新方式都是 l=mid、r=mid，而不是 l=mid+1、r=mid-1，在这个过程中 l/r 已经替代 res 完成了记录并更新答案的过程，便不需要额外再用一个变量来存储答案，当循环终止时 l==r，此时的 l/r 就在答案位置，直接输出 l/r 即可；而当循环条件为 l<=r 时，每次 mid 满足条件 l 和 r 都会更新到 mid 的下一位置，所以此时就需要一个 res 变量存储满足条件的位置（mid）并不断更新，res 最后一次更新的值便是答案，并且 while(l<=r) 终止时 l 和 r 不相等，不方便通过 l 和 r 返回答案。

4. 为什么当循环条件为 l<r 时 mid 的表达式是 (l+r+1)/2?什么时候需要加 1 什么时候不需要加？ 至于什么时候需要加 1，就记住就可以了：

当 while 循环条件写的是 l<r 时，如果是 l=mid，就需要加 1，如果是 r=mid 就不需要。

至于为什么呢，大家都知道 / 是向下取整，那么可以想一个极端的时候，当 l=r-1 的时候，此时区间为 [l,r]，mid=(l+r)/2=(l+l+1)/2=l，l=mid，更新后区间变为 [mid,r]，也就是 [l,r]，和原来一模一样，然后就会陷入无尽的死循环；而如果 +1 的话，mid=(l+r+1)/2=(l+l+1+1)/2=r，区间变为 [r,r] 循环终止，避免了死循环。而正因为 / 是向下取整，所以当 r=mid 时不 +1 也会直接更新成 [l,l]，所以不用加。

5. 为什么当循环条件为 l<r 时会出现 l=mid/r=mid 的时候，什么时候 l=mid+1/r=mid-1,什么时候 l=mid/r=mid? 这个要看实际情况，可以参考我代码上的两种情况，我分别给大家详细解析一下。

//在 a 数组中寻找第一个>=x 的数 a={1,2,2,2,3,3,3,4,5} x=3 初始状态： l=0 r=8 mid=(l+r)/2=4，答案区间 [0,8]
//此时 a[mid]=a[4]=3>=3(符合条件），这个时候的 mid 也是满足答案的，
//所以答案区间应该更新为 [0,4] 而不是 [0,4-1]，所以应该是 r=mid 而不是 r=mid-1
//其实我这个样例显而易见，如果 r=mid-1，那么直接就 WA 了，你直接把正确答案给扔出区间了
//我们继续对 [0,4] 进行二分，此时 mid=(0+4)/2=2;
//此时的 a[mid]=a[2]=2<x，此时的 mid 不满足答案，这个数和它之前的数就可以直接排除了，
//那他就不应该在答案区间中继续二分，下一次我们应该从 mid 的下一个数开始找
//即答案区间应更新为 [2+1,4]，所以应该是 l=mid+1
//这个时候如果你写的是 l=mid，那么会直接喜提死循环 

//在 a 数组中寻找最后一个<=x 的数 和上面的其实一样，我再举个样例 a={0,1,1,1,2,2,3,4,5} x=2 初始状态： l=0 r=8 mid=(l+r)/2=4，答案区间 [0,8]
//此时 a[mid]=a[4]=2<=2(符合条件），这个时候的 mid 也是满足答案的，
//所以答案区间应该更新为 [4,9] 而不是 [4+1,9]，所以应该是 l=mid 而不是 l=mid+1
//然后这时候你可以顺势把上面写的 (l+r)/2 改成 (l+r+1)/2//不改一会就死循环
//这又是一个极端的样例，如果 l=mid+1，那么直接就 WA 了，你直接把正确答案给扔出区间了
//继续二分，[4,9],mid=(4+9+1)/2=7;
//此时 a[mid]=a[7]=4>x ,不满足答案，直接排除，从它的下一个数开始找
//答案区间更新为 [4,7-1]，所以是 r=mid-1
//同样，如果你写的是 l=mid，那么喜提死循环 

如果题里是找第一个>x 的数，就直接把>=改成>就好了，灵活一点

2.4 例题

（一）P2249 【深基 13.例 1】查找

这题就是道二分查找的板题，相信大家都能写出来，直接奉上 AC 代码。

#include<iostream>
using namespace std;
const int N = 1000010;
int a[N], x, q, n;

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    while (q--) {
        cin >> x;
        int l = 1, r = n; //左右边界
        while (l < r) //因为是找第一次出现的位置，那就是尽量往左来，就用模板 1
        {
            int mid = l + r >> 1;
            if (a[mid] >= x) r = mid; //判断条件，如果值大于等于目标值，说明在目标值右边，尽量往左来
            else l = mid + 1;
        }
        if (a[l] != x) { //如果找不到这个值
            cout << -1 << ' ';
            continue;
        }
        cout << l << " ";
    }
    return 0;
}

（二）P1102 A-B 数对

思路：给出了 C，我们要找出 A 和 B。我们可以遍历数组，即让每一个值先变成 B，然后二分找对应的 A 首次出现位置，看是否能找到。 如果找到 A，那就二分找最后出现的位置，继而，求出 A 的个数，即数对的个数。

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 200010;
long long a[N], n, c, res, st;

int main() {
    cin >> n >> c;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n); //先排序
    for (int i = 1; i < n; i++) //遍历每一个 B
    {
        int l = i + 1, r = n; //寻找 A 第一次出现的位置，使得 A-B=C
        while (l < r) //因为是第一次出现，尽量往左找
        {
            int mid = l + r >> 1;
            if (a[mid] - a[i] >= c) r = mid; //判断：在目标值的右边，满足，往左来
            else l = mid + 1;
        }
        if (a[l] - a[i] == c) st = l; //能找到 C 就继续
        else continue;
        l = st - 1, r = n; //查找 A 最后出现的位置
        while (l < r) //因为是最后一次出现，尽量往右找
        {
            int mid = l + r + 1 >> 1;
            if (a[mid] <= a[st]) l = mid; //判断：在目标值的左边，满足，往右去
            else r = mid - 1;
        }
        res += l - st + 1; //最后出现的位置减首次出现的位置就是区间长度，即 A 的个数
    }
    cout << res;
    return 0;
}

三、二分答案

3.1.什么是二分答案

对于一个问题，它的答案属于一个区间，当这个区间很大时，暴力超时。但重要的是——这个区间是对题目中的某个量有单调性的，此时，我们就会二分答案。每一次二分会做一次判断（check 函数），看是否对应的那个量达到了需要的大小，如果满足 check，就放弃右半区间（或左半区间），如果不满足，就放弃左半区间（或右半区间）。一直往复，直至到最终的答案。

这么解释可能比较抽象，大家可以回想一下高中做选择题的时候，如果不会做，这个时候你是不是会运用排除法，把四个选项挨个往里带，如果 A B C D 是递增的，有时候是不是你把 C 带进去不对的同时把 D 也同时排除了。

举个例子 3+（）=7 A.2 B.4 C.9 D.11 E.12 F.17...
不会就选 C(bushi),我们先从 C 代，把 C 带进去都>7 了，那 C 后面的选项一定都是错的，可以直接排除 

这个过程其实就是一个简单的二分答案，排除答案的过程就是 check 的过程。

3.2.二分查找和二分答案有什么区别

二分查找：在一个已知的有序数据集上进行二分地查找 二分答案：答案有一个区间，在这个区间中二分，直到找到最优答案

3.3.二分答案模板

尽量往左找答案

//求最小的最大值
int bsearch_1(int l, int r) {
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

尽量往右找答案

//求最大的最小值
int bsearch_2(int l, int r) {
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

你会发现二分答案其实只是把二分查找的条件改成了 check，这个就是二分的通用模板，可以直接套板子应对绝大部分二分问题。

3.4.什么时候该使用二分答案

1、答案在一个区间内（一般情况下，区间会很大，暴力超时） 2、直接搜索不好搜，但是容易判断一个答案可行不可行 3、该区间对题目具有单调性，即：在区间中的值越大或越小，题目中的某个量对应增加或减少。 4、关键词：求…最大值的最小值、求…最小值的最大值、求满足条件下的最小（大）值、求最靠近一个值的值、求最小的能满足条件的代价…

3.5.怎样二分答案

1. 找具有单调性的答案区间（l= …,r=…）

   如何理解答案的单调性呢？观察图可以发现，位于答案左边的区间不满足条件，位于答案右边的区间满足条件，像这种要么一边不满足，要么一边都满足的现象就是答案的单调性。

   答案的单调性大多数情况下可以转化为一个函数，其单调性证明多种多样，如下：

   • 移动石头的个数越多，答案越大（NOIP2015 跳石头）。
   • 前 i 天的条件一定比前 i + 1 天条件更容易（NOIP2012 借教室）。
   • 满足更少分配要求比满足更多的要求更容易（NOIP2010 关押罪犯）。
   • 满足更大最大值比满足更小最大值的要求更容易（NOIP2015 运输计划）。
   • 时间越长，越容易满足条件（NOIP2012 疫情控制）。

2. 设计 check 函数 这个具体题目具体分析，可以看例题感受一下，究其根本还是要多做题，无他，唯手熟尔

3. 套模板 不用我多说了吧

3.6.例题

（一）P1873 [COCI 2011/2012 #5] EKO / 砍树

这道题目本质上就是要求一个最大高度的问题，使得砍到的树的总长度满足条件，拿样例 1 举例，展示出来就是这样的：

假设 ans 是满足条件的最大高度，那么在图片中展示就是这样的：

大于 ans 的高度，不满足条件，小于 ans 的高度，都满足条件，这样的答案具有单调性，所以考虑使用二分答案。

解题思路：

1. 找有单调性的答案区间： 我们要求一个满足条件的最大高度，那么答案的范围就应该是从 0 到树的最大高度 height，也就是 [0,height]。
2. 设计 check 函数 可以看出来这题是尽量向右（向上）找答案，这道题我们可以用一个变量 sum 存储得到的总长度，如果 sum 大于等于 m 就直接返回 true，否则返回 false.
3. 套模板

#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int n, m, a[N];

bool check(int x) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] > x) sum += a[i] - x;
        if (sum >= m) return true;
    }
    return false;
}

int main() {
    cin >> n >> m;
    int height = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        height = max(height, a[i]); //记录最大高度
    }
    int l = 0, r = height;
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid)) //判断是否达到要求的木材总量 m，更新区间
            l = mid;
        else r = mid - 1;
    }
    cout << l << endl;
    return 0;
}

（二）P1182 数列分段 Section II

解题思路：

这就是一道求最小的最大值的题。

1. 找有单调性的答案区间： 要求最大值最小，则该值必定大于数列中的最大值（最大值单独为一段的时候），最大值则为数列中所有数之和。所以最大值的区间 left=数列中的最大值，right=数列的所有数之和。
2. 设计 check 函数 需要两个变量，sum 表示当前这段中的数字总和，cnt 表示数列目前分了多少段，因为从 a[0] 一开始就是第一段，cnt 最少是一段，所以初始赋值为 1，具体见代码注释。
3. 套模板

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
long long n, m, a[N], maxn, sum;

bool check(long long x) {
    long long sum = 0, cnt = 1; //sum 表示当前这段中的数字总和，cnt 表示数列目前分了多少段
    for (int i = 0; i < n; i++) {
        if (sum + a[i] <= x) //判断 a[i] 是否可以放入当前这段
            sum += a[i];
        else {
            sum = a[i]; //否则 a[i] 自起一段，数列总段数 cnt+1
            cnt++;
        }
    }
    if (cnt <= m) return true;
    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        maxn = max(maxn, a[i]); //maxn 表示数组中元素的最大值
        sum += a[i]; //sum 表示数列中所有元素之和
    }
    long long l = maxn, r = sum;
    while (l < r) {
        long long mid = l + r >> 1;
        if (check(mid)) //更新区间
            r = mid;
        else l = mid + 1;
    }
    cout << l;
    return 0;
}

（三）P1824 进击的奶牛

解题思路

这就是一道求最大的最小值的题。

1. 找有单调性的答案区间： l 为 1，就是紧挨着，r 为 a[n-1]-a[0];
2. 设计 check 函数 和上一道题差不多，具体看注释
3. 套模板

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
long long n, m, a[N], maxn;

bool check(long long x) {
    int idx = 0, cnt = 1; //index 为当前坐标，cnt 为奶牛数量
    for (int i = 1; i < n; i++) {
        if (a[i] - a[idx] >= x) { //判断 a[i] 和当前坐标之前的差值
            idx = i; //条件成立，更新坐标，奶牛数量 +1
            cnt++;
        }
    }
    if (cnt >= m) return true;
    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n); //二分的题，一定不要忘了排序
    long long l = 1, r = a[n - 1] - a[0]; //最小值为 1，就是紧挨着，最大值为最后一个坐标减第一个坐标
    while (l < r) {
        long long mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l;
    return 0;
}

什么时候往左找，什么时候往右找？

精髓

精髓就在于：尽可能这三个字。

例子 1

比如数组 a[] = {0, 1, 1, 1, 2, 2, 3, 4, 5} 找最后一个 ≤ 2 的数，mid = 4，指向第一个 2，满足条件，这个时候你是不是想再往右找看看右面还有没有满足的？ 因为要找 最后一个，也就是尽可能向右找。 就 l = mid。

例子 2

再来看砍树那道题。 他要 M 的木材，还要尽可能少砍一点，也就是尽可能高。 他如果锯片在 a[mid] 的地方就已经能得到 m 的木材了，那就继续往上升看看能不能更高点，就 l = mid（继续往上搜）。

总结

他要最大值尽可能小。 既然是尽可能小。 那就是满足条件时 r = mid，看看能不能再小点。 满足条件的时候就往不满足条件那个方向移，不满足条件的时候就往满足条件的方向移。 满足条件的时候就是 if(check(mid)) 后面跟的。 这就是二分答案。

四、浮点数二分（实数二分）

4.1.模板

思路和整数二分一样，区别是浮点型二分不需要注意边界问题（也就是不需要 +1/-1）。

while (r - l > 1e-5) //需要一个精度保证
{
    double mid = (l + r) / 2;
    if (check(mid)) l = mid; //或 r=mid;
    else r = mid; //或 l=mid;
}

4.2 例题

（一）数的三次方根

题目描述 给定一个浮点数 n，求它的三次方根。

输入格式 共一行，包含一个浮点数 n。

输出格式 共一行，包含一个浮点数，表示问题的解。 注意，结果保留 6 位小数。

数据范围 −10000 ≤ n ≤ 10000

输入样例：

1000.00

输出样例：

10.000000

ACcode

#include<iostream>
using namespace std;

int main() {
    double x;
    cin >> x;
    double l = -100, r = 100; //根据题目范围 开三次方根 估计答案大概范围
    while (r - l > 1e-8) {
        double mid = (l + r) / 2;
        if (mid * mid * mid >= x) r = mid;
        else l = mid;
    }
    printf("%.6lf\n", l);
    return 0;
}

五、lower_bound 和 upper_bound

这两个是 C++ 的 STL 库封装的两个二分查找函数，使用时需要加上头文件。

#include<algorithm>

使用方法和 sort 函数很像，可以用 greater< type > 重载，也可以自定义比较函数，具体可以翻阅相关博客，在这里只简单介绍一下基本的使用方法。

upper_bound

upper_bound(begin, end, value)//在从小到大的排好序的数组中，在数组的 [begin, end) 区间中二分查找第一个大于 value 的数，找到返回该数字的地址，没找到则返回 end。
upper_bound(begin, end, value, greater<int>())//在从大到小的排好序的数组中，在数组的 [begin, end) 区间中二分查找第一个小于 value 的数，找到返回该数字的地址，没找到则返回 end。

lower_bound

lower_bound(begin, end, value)//在从小到大的排好序的数组中，在数组的 [begin, end) 区间中二分查找第一个大于等于 value 的数，找到返回该数字的地址，没找到则返回 end。
lower_bound(begin, end, value, greater<int>())//在从大到小的排好序的数组中，在数组的 [begin, end) 区间中二分查找第一个小于等于 value 的数，找到返回该数字的地址，没找到则返回 end。

注意，返回的是地址，不是下标，也不是数值！！！

如果你直接输出，那么你会得到这样一串东西（地址）。

接下来举个例子，讲解一下在实际中怎么用。

#include<iostream>
#include<algorithm>
using namespace std;

int main() {
    int a[] = {1, 2, 3, 3, 3, 4, 4, 5, 6};
    int x = 3; //查找第一个>x 的元素，并输出其下标
    cout << upper_bound(a, a + 9, x) - a; //输出 5（下标）
    // 查找第一个>x 的元素，并输出其数值
    auto i = upper_bound(a, a + 9, x);
    cout << *i; //输出 4（数值）
    //查找第一个>=x 的元素，并输出其下标
    cout << lower_bound(a, a + 9, x) - a; //输出 2（下标）
    // 查找第一个>=x 的元素，并输出其数值
    auto j = lower_bound(a, a + 9, x);
    cout << *j; //输出 3（数值）
}

该函数的前两个参数及其重载方式和 sort（）函数差不多，如果不了解的话可以去学习一下 sort（）的相关语法，类比一下就懂了。

六、练习题

相信大家已经正式入门二分了，接下来可以做几道题练习一下。

• P1678 烦恼的高考志愿
• P1163 银行贷款
• P8647 [蓝桥杯 2017 省 AB] 分巧克力
• P1024 [NOIP2001 提高组] 一元三次方程求解
• P2440 木材加工
• P1577 切绳子
• P2678 [NOIP2015 提高组] 跳石头
• 1460. 我在哪？
• 102. 最佳牛围栏

七、总结

二分模板一共有两个，分别适用于不同情况。 算法思路：假设目标值在闭区间 [l, r] 中，每次将区间长度缩小一半，当 l = r 时，我们就找到了目标值。

当我们将区间 [l, r] 划分成 [l, mid] 和 [mid + 1, r] 时，其更新操作是 r = mid 或者 l = mid + 1;，计算 mid 时不需要加 1。

int bsearch_1(int l, int r) {
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

当我们将区间 [l, r] 划分成 [l, mid - 1] 和 [mid, r] 时，其更新操作是 r = mid - 1 或者 l = mid;，此时为了防止死循环，计算 mid 时需要加 1。

int bsearch_2(int l, int r) {
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}