浅谈二分|这个二分为什么又双叒叕死循环了

众所周知，二分查找是一种针对有序集合快速进行查找的算法，时间复杂度为$O(logn)$，并且由此还衍生出了OI中常用的二分答案。但是，在手动实现二分时，常常有许多细节令人感到困惑，本文将对它们进行一些简单的梳理。

手写二分的一般思考过程

丢个例题，借这个例子更直观地进行梳理

例题：已知一个长度为$n$的数组，把它切分成$m$个连续的段，使得每段之和的最大值最小。求这个最小值。

这是一道二分答案的经典问题，只需要二分地枚举每段之和的最大值，然后$O(n)$地检查在保证这个值为mid的情况下是否能够切成$m$段即可。

对于具体的细节，我们分成三个步骤，进行如下分析：

1. 确定mid是否可能是答案

在上面的题目中，不妨记在每段最大值为mid的情况下，最少可以将数组分成$minSeg(mid)$段。那么显然，如果$minSeg(mid) > m$，那么说明mid不符合题意，不可能成为答案；如果$minSeg(mid) \leq m$，那么mid是符合题意的，但不一定是最小值，也就是说mid可能成为答案。

平常在写的时候，经常把这个过程整理成一个函数bool check(mid)，check(mid) == true就表示mid可能成为答案。

2. 确定答案在mid左侧还是右侧

在本题中，如果mid可能成为答案，那么由于我们要求最小值，所以真正的答案只会$\leq mid$；如果mid不可能是答案，那么真正的答案应该$> mid$（这都是由本题的答案本身的具有单调性质保证的）。

于是我们有代码：

int l = 0, r = INT_MAX;
while (l < r) {
    int mid = (l + r) / 2;
    if (minSeg(mid) <= m) 
        r = mid;
    else
        l = mid + 1;
}
cout << l << endl;

我们一般是认为答案位于$[l, r]$（注意是闭区间）里的，答案$\leq mid$就表现为将区间变成$[l,mid]$；而答案$>mid$就表现为将区间变成$[mid+1,r]$。

相应的，如果是其他题目，可能会出现相反的情况，即如果mid可能成为答案，真正的答案$\geq mid$；如果mid不可能是答案，那么真正的答案$< mid$（比如要让某个最小值最大化）。这时候对应的区间改变就是$[mid, r]$和$[l, mid-1]$。

3. 考虑(l + r) / 2的取整问题

此处对于初学者需要重点关注，二分死循环问题大多出在此处。

一般有两种常见的写法：mid = (l + r) / 2（向下取整）和mid = (l + r + 1) / 2（向上取整）。这两种写法不会影响二分的时间复杂度，但是有可能导致死循环，需要搭配正确的情况使用。

比如本题中，我们使用的是第一种，这是十分正确的。但假设我们遇到前文所说的相反的情况，那么我们就应该使用第二种。举例如下：

int l = 0, r = INT_MAX;
while (l < r) {
    int mid = (l + r + 1) / 2;
    if (mid可能是答案) 
        l = mid;
    else
        r = mid - 1;
}
cout << l << endl;

如果你一不小心，仍然使用了向下取整的写法，你就可能一直执行l = mid循环个不停。

如果实在记不住对应的情况，可以就假设某个时刻$r = l + 1$，然后尝试进入两个条件分支，检查是否会出现死循环的情况。

几种经典的二分板子

最后对几种经典的二分板子进行一个梳理。首先是上面提到的两种：

int l = 0, r = INT_MAX;
while (l < r) {
    int mid = l + ((r - l) >> 1);  // 基本等价于(l+r)/2，唯一的区别是l+r可能会造成溢出
    if (check(mid)) 
        l = mid + 1;
    else
        r = mid;
}
cout << l << endl;

int l = 0, r = INT_MAX;
while (l < r) {
    int mid = (l + (r - l + 1)) >> 1;  // 同上
    if (check(mid)) 
        l = mid;
    else
        r = mid - 1;
}
cout << l << endl;

还有一种写法，和上面两种略有差别，但其实这种可能更加直观一些。例如要在一个递增数组里查找某个数$key$：

int l = 0, r = n, ans = -1;  // 没找到就是-1
while (l <= r) {
    int mid = (l + r) / 2;
    if (arr[mid] < key) {
        l = mid + 1;
    } else if (arr[mid] > key) {
    	r = mid - 1;
    } else {  // arr[mid] == key，即已经找到
    	ans = mid;
    	break;
    }
}
cout << ans << endl;

也可以遍查找边更新答案：

int l = 0, r = n, ans = -1;  // 没找到就是-1
while (l <= r) {
    int mid = (l + r) / 2;
    if (check(mid)) {
    	ans = mid;
        l = mid + 1;
    } else if (arr[mid] > key) {
    	r = mid - 1;
    }
}
cout << ans << endl;

总结

总之，二分的写法千变万化，要根据具体的情况灵活套用合适的板子，否则就有可能坠入死循环和debug的深渊。

受笔者知识水平和表达能力所限，有的问题难免解释得或啰嗦或不清楚，欢迎在评论区指正