‍

二分只有几行代码，改一道题却又要重新考虑等号放哪边、端点要不要加一。我觉得红蓝分区的解释有用，就在于它把这些细节放回了同一个问题：我们究竟已经知道哪些位置属于哪一侧？只要循环一直保留这份信息，停止条件和返回值就可以从含义中推出来。

1. 红蓝分区

先假设我们检查的性质具有单调性，按位置从左往右，只会发生一次真假切换。把左侧叫作红区、右侧叫作蓝区，并维护 left​ 属于红区、right​ 属于蓝区。中间的开区间是尚未确定的部分，每次检查一个 mid，就能根据单调性排除其中一半。

图 1：二分循环维持左右端点的颜色不变。 来源：二分查找视频。

如果整个数组都是蓝色，红区中根本没有真实元素，我们该把 left 放在哪里？可以给数组外补两个虚拟位置：对下标 $[0,n-1]$，约定 $-1$ 属于红区，$n$ 属于蓝区。它们只用于表达两侧的已知信息，不会拿来访问数组。因此无论真实数组中有没有红色或蓝色元素，都能使用同一套初值。

图 2：虚拟端点只承担区间不变量，不会被访问。 来源：二分查找视频。

int left = -1;
int right = n;

while (left + 1 < right) {
    int mid = left + (right - left) / 2;

    if (check(mid)) {
        left = mid;      // mid 属于左侧
    } else {
        right = mid;     // mid 属于右侧
    }
}

为什么更新时可以直接写 left = mid​，不用加一？因为我们要保留的是一个已知红色的位置，mid​ 恰好满足这个要求。蓝色一侧同理。两个端点相邻时，尚未确定的开区间为空，left​ 就是最后一个红色位置，right 就是第一个蓝色位置；最后根据题意选择其中一个。

图 3：每轮把 mid​ 归入一侧，区间最终缩到相邻位置。 来源：二分查找视频。

2. 四种常见查询

把这套含义放进升序数组，我们就能得到熟悉的查找函数。要找第一个大于等于 target​ 的位置，就把 < target​ 归到红区，把 >= target​ 归到蓝区。问题要的是第一个蓝色位置，所以返回 right。

int lowerBound(const vector<int>& nums, int target) {
    int left = -1, right = nums.size();

    while (left + 1 < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) left = mid;
        else right = mid;
    }

    return right;
}

寻找第一个大于 target​ 的位置，只需把判断改成 nums[mid] <= target​。最后一个小于目标值的位置是 lowerBound(nums, target) - 1​；最后一个小于等于目标值的位置是 upperBound(nums, target) - 1。

精确查找也可以先求 lowerBound​，再判断返回位置是否越界且值等于 target。这种写法把等于目标值的情况归到同一侧，通常比单独写三路判断更稳定。

3. 二分答案

有些题需要在答案范围中寻找可行与不可行的分界。只要 check(x) 具有单调性，就可以二分答案。例如最小化最大负载时，给定上限 $x$ 后可以判断是否能在限制内完成；若 $x$ 可行，更大的上限也可行。

写这类题时，二分本身通常不难，主要工作是证明单调性，并确认 check 的复杂度。若检查一次需要 $O(n)$，答案范围为 $V$，总复杂度通常为 $O(n\log V)$。

4. 两个有序数组的中位数

中位数题容易让人把元素下标、切分位置和取出的个数混在一起。我们先不找中位数本身，改为把两个数组共同分成左、右两半：左半的元素都不大于右半，并且两边数量合适。设数组长度分别为 $m$、$n$，通过交换保证 $m\le n$，左半需要包含

$$k=\left\lfloor\frac{m+n+1}{2}\right\rfloor$$

个元素。若从第一个数组取前 $i$ 个，从第二个数组取前 $j=k-i$ 个，那么合法分割应满足

$$A_{i-1}\le B_j,\qquad B_{j-1}\le A_i$$

这两个条件就够了，因为同一个数组内的左右顺序本来已经成立，我们只需检查跨数组的大小关系。某一侧为空时，用 $-\infty$ 或 $+\infty$ 代替不存在的端点。这里二分的是个数 $i\in[0,m]$，所以虚拟开区间是 $(-1,m+1)$，比二分下标多了一个合法位置。

还要确认 $j=k-i$ 不会越界。由 $m\le n$，有 $m\le k\le n$，因此 $0\le k-i\le n$。这就是先对较短数组二分的另一个好处。合法切分可能不止一个，代码找到任意一个便能返回答案，不必强求唯一切分点。

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        if (m > n) return findMedianSortedArrays(nums2, nums1);

        int k = (m + n + 1) / 2;
        int left = -1, right = m + 1;

        while (left + 1 < right) {
            int i = left + (right - left) / 2;
            int j = k - i;

            int aLeft  = (i == 0) ? INT_MIN : nums1[i - 1];
            int aRight = (i == m) ? INT_MAX : nums1[i];
            int bLeft  = (j == 0) ? INT_MIN : nums2[j - 1];
            int bRight = (j == n) ? INT_MAX : nums2[j];

            if (aLeft <= bRight && bLeft <= aRight) {
                int leftMax = max(aLeft, bLeft);
                if ((m + n) % 2 == 1) return leftMax;

                int rightMin = min(aRight, bRight);
                // 先转为 double，避免两个 int 相加时溢出
                return (static_cast<double>(leftMax) + rightMin) / 2.0;
            }

            if (aLeft > bRight) right = i;
            else left = i;
        }

        return 0.0;
    }
};

若 aLeft > bRight，我们再增加 $i$，只会让第一个数组的左端最大值更大、第二个数组的右端最小值更小，所以必须向左找。另一种不合法情形 bLeft > aRight 则要求向右找。两个方向都有单调性依据。找到合法切分后，奇数长度取左半最大值，偶数长度取左半最大值与右半最小值的平均。假设总长度至少为 $1$，总时间为 $O(\log(\min(m,n)+1))$，额外空间为 $O(1)$。

5. 写代码前先确定不变量

比起背加一减一，我更倾向于先在代码旁写清楚左右端点的含义。更新某个端点时，我们是在增加一条确定的信息；停止时，再检查这份信息能否直接给出答案。中位数题也遵循这个思路，只是搜索对象换成了取出的元素个数。先把对象说清楚，许多看似特殊的边界处理就有了统一的解释。

参考资料：从红蓝分区理解二分查找；C++ Reference, lower\_bound​ 与 upper\_bound。