二分总结

序

以前学习二分的时候一直没有搞清楚什么时候$mid = (left + right) / 2$，什么时候$mid = (left + right + 1) / 2$，更新的时候是$right = mid + 1$还是$right = mid - 1$，但是一直迷迷糊糊的也能写对题，后面也没有多管。这个寒假重新学一遍基础算法，才明白为什么会有这两种情况。

整数二分的两种情况

第一种 $mid=(right+left+1)/2$
这种情况代码如下

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

为什么$mid$需要补上一个$1$呢？

因为整数的除法是向下取整，我们需要在运算时+1时它变成向上取整，否则的话会因为边界问题导致while无限循环。
举个例子，在区间只有两个数的时候，比如$l=3，r=4，mid=(3+4)/2=3$，这时候如果check成功，那么会执行$l=mid$，然后问题就来了，$l$和$mid$本来就都等于3，然后就会无限循环下去，$l$和$mid$的值永远不会更新。所以在$l=mid,r=mid-1$的更新方式下，我们需要将运算时$mid+1$成为向上取整才不会死循环。

第二种 $mid=(right+left)/2$
这种情况代码如下

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

为什么$mid$在这里不需要补上一个$1$呢？

因为边界问题不会影响到值的更新，还是用上面那个例子，$l=3，r=4，mid=(3+4)/2=3$。
此时如果check成功，那么$l=mid+1=4$，更新成功。如果check失败，则$r= mid=3$，同样更新成功。由此可以看出，在$l=mid+1,r=mid$的更新方式下，不需要对$mid$进行任何操作。

以上是整数二分的两种固定写法。那么什么时候用哪种方法呢，这就要根据具体的题目进行分析了。

例题—— 分巧克力

题目描述

儿童节那天有 K 位小朋友到小明家做客。
小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 N 块巧克力，其中第 i 块是 Hi×Wi 的方格组成的长方形。
为了公平起见，小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。
切出的巧克力需要满足：
形状是正方形，边长是整数
大小相同
例如一块 6×5 的巧克力可以切出 6 块 2×2 的巧克力或者 2 块 3×3 的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？

输入格式

第一行包含两个整数 N 和 K。
以下 N 行每行包含两个整数 $H_i$ 和 $W_i$。
输入保证每位小朋友至少能获得一块 $1×1$ 的巧克力。

输出格式

输出切出的正方形巧克力最大可能的边长。

输入输出样例

输入#1
2 10
6 5
5 6

输出#1
2

AC代码

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <stack>
typedef long long ll;
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define endl '\n'
using namespace std;
int n, k;
const int N = 1e5 + 10;
int h[N], w[N];

bool check(int x)
{
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        cnt += (h[i] / x) * (w[i] / x);
        if (cnt >= k)
            return true;
    }
    return false;
}

int main()
{
    IOS;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> h[i] >> w[i];
    int l = 0, r = N;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }
    cout << l << endl;
    return 0;
}

题目很简单是二分的板子题，主要是说为什么要用第一种求$mid$方法呢。
为什么二分里面不能写成

int mid = l + r >> 1;
if (check(mid))
     l = mid + 1;        //这样写跑样例答案是3
else
     r = mid;

推导一遍发现，如果$check$成立后，说明当前的$mid$值也是在答案范围中，所以答案只能在$[mid,
r]$之中取。理所当然无法用上面那种写法，如果用上面那种方法，$l$会直接更新成$mid+1$，会越过$mid$这个值，所以在一些情况就会出现错误，比如题面的样例$l$就会成为$2+1=3$，越过了$2$这个可能的答案值，恰好$2$就是最大的一个答案，导致答案错误。

总结

这次弄明白了二分的写法属实是不易，留文一篇防止日后遗忘
以后写二分的时候记得注意一下区间情况