开区间与循环不变量

二分查找的思想一句话能说清：在有序序列里每次将范围减半，$O(\log n)$ 步定位目标。真正写对它却出了名的难，边界取 $c$ 还是 $c \pm 1$、循环条件用 < 还是 <=、找不到时返回什么、要找的是等于还是第一个大于等于，稍有不慎就 off-by-one 或死循环。本页不背模板，而是用一个循环不变量把所有变体统一起来。

1 · 开区间与红蓝染色

二分难写，难在边界。与其逐条记忆什么时候 +1、什么时候 <=，不如抓住一个贯穿始终的命题：用两个指针把数组划成三段，红段（确定属于一类）、蓝段（确定属于另一类），以及夹在中间的待定段。只要每一轮后红蓝段的含义不变、待定段严格缩小，循环结束时答案必然落在红蓝交界处。

本页采用开区间写法，取 $l = -1$、$r = n$，始终维持 $(l, r)$ 是唯一的待定区间：下标 $\le l$ 的全染红、$\ge r$ 的全染蓝。初始时整个数组都待定，两端的虚拟哨兵 $-1$ 与 $n$ 天然满足红蓝条件，因为空集上任何命题都成立。本节以最常用的 lower_bound 为例，即找第一个 $\ge$ target 的下标，于是红是「小于 target」、蓝是「大于等于 target」。

三条命题在 $l = -1$、$r = n$ 时平凡成立，因为红蓝段都是空集；每一步无论走哪个分支都不破坏它们；当 $l + 1 = r$ 时待定段为空，答案被夹到唯一的 $r$。初始成立、每步保持、终止时可读出答案，这三段构成它正确性的全部论证。

终止条件写作 $l + 1 < r$ 也出自同一处：开区间 $(l, r)$ 里的待定元素个数是 $r - l - 1$，只要它不小于 1 就还有元素要判，一旦 $l + 1 = r$ 就该停。又因为 $c$ 严格落在 $(l, r)$ 内，即 $l < c < r$，每轮 $l$ 或 $r$ 必向中间挪至少一格，区间真正在缩小，不会死循环。§3 与闭区间写法对比时，这一点是关键。

2 · 四种边界查询的统一模板

实战里二分常不是找等于 target，而是找一个边界：第一个 $\ge$、第一个 $>$、最后一个 $\le$、最后一个 $<$。它们看似要背四份代码，在 §1 的开区间模板下却只有两个可变之处。其一是红条件，即把 $c$ 并入红段的判定，只有 a[c] < target 与 a[c] <= target 两种，它决定分界线落在 target 的哪一侧。其二是返回端，即循环结束于 $l + 1 = r$ 时取第一个蓝 $r$ 还是最后一个红 $l$。两条判定乘两个返回端得到四种查询，循环主体一字不改。

四者两两对偶。同一条红条件下，$r$ 与 $l$ 恰好是分界线两侧紧邻的一对：「第一个 ≥」与「最后一个 <」共用红条件 a[c] < target，两者答案相邻，即 $r = l + 1$；「第一个 >」与「最后一个 ≤」共用 a[c] <= target。记住其中一个（通常是 lower_bound），另外三个都能当场推出来。

这张表与下面几条派生式经穷举对拍验证过：长度 0 到 6、值域 0 到 4 的全部非降序列，配上 $-1$ 到 5 的全部 target，四种查询共 12936 例与线性扫描的结果逐一相符；派生恒等式在同一组数据的 3234 组上也无一例外。

3 · 三种区间写法及其边界陷阱

同一个 lower_bound，区间的开闭约定可以有三套，各自的循环条件、$c$ 的归属、收缩方式都不同，这正是二分容易写错的根源。三种写法是：开区间 $(l, r)$ 两端都不含、左闭右开 $[l, r)$ 含左不含右、闭区间 $[l, r]$ 两端都含。它们答案必然一致，中间机制却各异。

区别全在待定区间用什么端点表示。开区间最对称，$c$ 永远不取端点，收缩时直接写 $l = c$ 或 $r = c$；半开与闭区间因为端点是含的，已判过的 $c$ 必须排除在外，才出现 $c + 1$ 与 $c - 1$。本页统一用开区间，图的就是不必记这些加减：条件永远是 $l + 1 < r$，收缩永远是 $l = c$ 或 $r = c$。

4 · 单调谓词上的二分答案

二分查找的本质不是在数组里找数，而是在一段单调的真值序列上找那个分界点。数组有序只是制造单调性的一种方式：只要存在一个判定 $f(x)$，它随 $x$ 增大只会从假变真或从真变假一次，就能直接在答案区间上二分，不必先有排好序的数组。

经典例子是整数平方根：求最大的 $x$ 使 $x^2 \le N$。判定 $f(x) = (x^2 \le N)$ 显然单调，$x$ 越大越难成立，真值序列形如若干个真接若干个假。于是「最后一个使 $f$ 为真的 $x$」就是答案，正是 §2 表里的「最后一个 ≤」。

值得注意的是，整个过程从不真的开一个长度 $N$ 的数组，$x^2$ 是用到时当场算的，区间 $[0, N]$ 只是逻辑上的搜索空间。

识别一个问题能否二分答案只看单调性。把问题改写成判定句「$x$ 是否可行」，若可行性随 $x$ 单调，即可行的都不超过某阈值或都不低于某阈值，就能二分那个阈值。把求最优值转成判定某个值是否可行，是这类题的统一套路，最大化最小值与最小化最大值（如把序列分成 $k$ 段使最大段和最小）、限速可行性、值域上的第 $k$ 小都是它的变体。

复杂度的维度也随之变了。数组二分是 $O(\log n)$，$n$ 是元素个数；二分答案是 $O(\log V \cdot T)$，$V$ 是答案的取值范围、$T$ 是单次判定的代价，搜索的是答案范围而非数据规模。上例中 $V = N$、判定是一次乘法即 $T = O(1)$，故总代价 $O(\log N)$；若判定本身要扫一遍数据，总复杂度就是 $O(n \log V)$。

无论是有序数组里的 lower_bound 还是本节抽象的 $f(x)$，用的都是同一套开区间加循环不变量，差别只在红蓝由谁定义：数组里由 a[c] 与 target 比较给出，二分答案里由谓词 $f(c)$ 直接给出。