整数二分入门与模板总结

1. 什么是整数二分

很多同学刚学二分时，会觉得二分就是“在有序数组里找某个数”。其实这只是最基础的一种用法。
从更本质的角度看，二分是在一段有规律的区间中，去寻找那个“分界点”。

对于整数二分来说，我们通常研究的是一个函数 check(x)，它表示“x 是否满足某种性质”。如果随着 x 的变化，check(x) 的结果具有单调性，那么就可以使用二分。

例如：

false false false true true true

这种情况说明：前面都不满足，后面都满足。我们就可以二分出第一个满足条件的位置。

再比如：

true true true false false false

这种情况说明：前面都满足，后面都不满足。我们就可以二分出最后一个满足条件的位置。

所以，整数二分的核心并不是背代码，而是先判断：

check(x) 是否具有单调性；
我要找的是左边界还是右边界。

2. `check(x)` 是什么

在二分模板中，通常会写这样一个函数：

bool check(int x) {/* ... */}

它的作用是：判断 x 是否满足题目的要求。

你可以把它理解成一个判断器。二分的过程其实非常简单，就是不断取一个中间值 mid，然后问：

mid 满足条件吗？

如果满足，就往某一边继续缩小区间；如果不满足，就往另一边缩小区间。最终区间缩到只剩一个点时，这个点就是答案。

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;
}

它适合处理这样的情况：

false false false true true true

也就是说，我们想找到第一个 true 出现的位置。

为什么 check(mid) 为真时要写 r = mid？
因为既然 mid 已经满足条件，那么答案有可能就是 mid，也有可能在 mid 左边，所以不能把 mid 丢掉，只能把右边界缩到 mid。

为什么 check(mid) 为假时要写 l = mid + 1？
因为如果 mid 不满足条件，那么答案一定不可能在 mid，只能出现在右边，所以直接把左边界更新为 mid + 1。

这套模板可以概括为：

找第一个满足条件的位置；
mid 向下取整；
条件成立时，收缩右边界。

4. 第二种模板：找右边界

第二种模板适用于寻找最后一个满足条件的位置。

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;
}

它适合处理这样的情况：

true true true false false false

也就是说，我们想找到最后一个 true 出现的位置。

为什么 check(mid) 为真时要写 l = mid？
因为既然 mid 满足条件，那么答案有可能就是 mid，也有可能还在 mid 的右边，所以要保留 mid，并继续去右边找。

为什么 check(mid) 为假时要写 r = mid - 1？
因为如果 mid 不满足条件，那么答案不可能在 mid，只能在它左边，所以把右边界缩到 mid - 1。

这套模板可以概括为：

找最后一个满足条件的位置；
mid 向上取整；
条件成立时，收缩左边界。

5. 为什么第二种模板一定要 `+1`

这是初学者最容易写错的地方。

第二种模板中，mid 的写法是：

int mid = l + r + 1 >> 1;

这里的 +1 不能省略，因为它的作用是让 mid 向上取整。

假设当前区间是：

l = 3, r = 4

如果你写成：

int mid = l + r >> 1;

那么结果就是：

mid = 3

如果此时 check(mid) 为真，就会执行：

l = mid;

也就是 l 仍然等于 3，区间没有缩小，程序就可能陷入死循环。

而如果写成：

int mid = l + r + 1 >> 1;

那么：

mid = 4

这时区间就能正常缩小。

所以，第二种模板必须牢记：mid 一定要向上取整。

6. 两种模板如何区分

很多同学背模板的时候最容易混淆，其实可以直接这样记：

如果要找第一个满足条件的位置，就用第一种模板；
如果要找最后一个满足条件的位置，就用第二种模板。

进一步对应到两种典型形式：

false false false true true true

找第一个 true，用第一种模板。

true true true false false false

找最后一个 true，用第二种模板。

所以，先不要急着写代码，先判断你到底在找哪一个边界。

7. 模板总结

最后把两套模板放在一起，方便直接记忆。

7.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;
}

适用情形：

false false false true true true

7.2 找最后一个满足条件的位置

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;
}

适用情形：