binary-search · 循环不变量

开区间 + 循环不变量：统一四种查询与二分答案

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

核心是开区间写法 $l = -1, r = n$ : 始终维持 (l, r) 为唯一「尚未确定」的区间，把 l 及其左侧染红、r 及其右侧染蓝。每一步取中点 c 判定它该染红还是染蓝，区间随之收缩，直到 l + 1 == r 再无待定元素。届时 l 是最后一个红、r 是第一个蓝——四种查询只是从这两端里取其一。本页串起四节：开区间与红蓝染色 → 四种查询 → 边界陷阱 → 二分答案。

1 · 开区间与红蓝染色：为什么这样写不会错

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

这里采用开区间写法： $l = -1, r = n$ ，始终维持 (l, r) 是唯一的待定区间——下标 <= l 的全染红、>= r 的全染蓝。初始时整个数组都待定，两端的虚拟哨兵 $-1$ 与 n 天然满足红/蓝（空集恒成立）。本节演示最常用的查询 lower_bound: 找第一个 >= target 的下标，于是「红 = < target」「蓝 = >= target」。

默认在 1, 3, 4, 7, 7, 9, 11, 15 里找第一个 >= 7 的位置。注意每一步只判定一个中点 c，它要么并入红段 (l = c)、要么并入蓝段 (r = c)，待定区间每轮约减半。试试把 target 改成数组里没有的值（如 8）, r 给出的就是「该插入的位置」。

不变量 (invariant) 到底是什么？ 整个循环自始至终维持三条恒真命题：其一，下标 <= l 的元素都 < target；其二，下标 >= r 的元素都 >= target；其三，答案（第一个 >= target 的下标）落在 (l, r] 内。初始 $l = -1, r = n$ 时三条平凡成立（红/蓝段都为空）；每一步无论走哪个分支都不破坏它们；当 l + 1 == r 待定段为空，答案被夹到唯一的 r。这套「不变量初始成立 + 每步保持 + 终止可读出答案」就是它正确性的全部。

为什么终止条件是 l + 1 < r? 开区间 (l, r) 里的待定元素个数是 $r - l - 1$ 。只要它 >= 1（即 l + 1 < r）就还有元素要判；一旦 l + 1 == r，待定段为空，该停。且因为 c 严格落在 (l, r) 内 (l < c < r)，每轮 l 或 r 必向中间挪至少一格，区间真正在缩小，绝不会死循环——这点在边界陷阱一节与闭区间写法对比时尤其关键。

把红蓝条件一换、返回端一改，这同一段循环就能回答「第一个 >」「最后一个 <=」「最后一个 <」乃至「精确等于」——见四种查询一节。

2 · ≥ / > / ≤ / <：一套模板，四个出口

实战里二分常不是「找等于 target」，而是找一个边界: 第一个 >= target、第一个 > target、最后一个 <= target、最后一个 < target。它们看似要背四份代码，其实在开区间模板下只有两个可变之处：

其一，红条件——把 c 并入红段的判定，只有两种：a[c] < target 或 a[c] <= target；它决定了红蓝的分界线落在 target 的哪一侧。其二，返回端——循环结束于 l + 1 == r 时，取第一个蓝 r 还是最后一个红 l。两条判定 × 两个返回端 = 四种查询，循环主体一字不改。下面切换查询类型，观察这两处如何联动。

2.1 · 四种查询一览

查询	含义	红条件 (l = c)	返回端	不存在时
第一个 ≥	lower_bound	`a[c] < target`	r	`r == n`
第一个 >	upper_bound	`a[c] <= target`	r	`r == n`
最后一个 ≤	—	`a[c] <= target`	l	$l == -1$
最后一个 <	—	`a[c] < target`	l	$l == -1$

四者两两对偶。 同一条红条件下，r 与 l 恰好是分界线两侧紧邻的一对：「第一个 ≥」与「最后一个 <」共用红条件 a[c] < target，答案互为相邻 (r == l + 1)；「第一个 >」与「最后一个 ≤」共用 a[c] <= target。所以记住一个（通常是 lower_bound），另外三个都能当场推: 换条件的等号、或换返回端。

精确等于怎么办？(LeetCode 704) 先求 r = lower_bound(target)，再判一次 r < n && a[r] == target: 成立则 r 是 target 首次出现的位置，否则不存在。区间计数同理：== target 的个数 = upper_bound(target) $-$ lower_bound(target)，一次都不用线性扫。

边界右移一格还能化简：「最后一个 < target」= lower_bound(target) $- 1$ ，「最后一个 <= target」= lower_bound(target + 1) $- 1$ （整数场景）。因此工程上常只实现 lower_bound 一个原语，其余皆由它派生——正是 std::lower_bound 的设计。

3 · 三种区间写法、整型溢出与死循环

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

3.1 · 三套模板，哪里不一样

三者一一对应： 区别全在「待定区间用什么端点表示」。开区间最对称——c 永远不取端点，收缩时直接 l = c / r = c；半开与闭区间因为端点是含的，已判过的 c 必须排除在外，才出现 c + 1 / $c - 1$ 。本系列其余节统一用开区间，就是图它不用记 ±1: 条件永远是 l + 1 < r，收缩永远是 l = c 或 r = c。

陷阱一：整型溢出。 教科书爱写 c = (l + r) / 2。当 l + r 超过 int 上限（约 21 亿）时会溢出成负数, $a[c]$ 直接越界。2006 年 Google 的 Joshua Bloch 撰文指出，几乎所有教科书与标准库的二分都带这个 bug，潜伏了近二十年。稳妥写法 $c = l + (r - l) / 2$ 永不溢出（ $r - l$ 必定在范围内）。JS 的 Number 没有这个上限，但在 C / C++ / Java 里这是必须的。

陷阱二：死循环。 当区间只剩两个元素、c 算出来恰好等于 l 时，若写成 l = c（而非闭/半开里的 l = c + 1）, l 原地不动，循环永远停不下来。开区间能规避它，是因为终止条件是 l + 1 < r 且 c 严格落在 (l, r) 内 (l < c < r)——每轮 l 或 r 必向中间挪至少一格。半开 / 闭区间则依赖 $c \pm 1$ 来保证前进，漏写就死锁。所以「循环条件」与「收缩量」必须配套，不能随意搭配。

怎么选？ 三套都对，但每个人固定用一套最不易错。开区间的优点是边界规则最少（无 $\pm 1$ ）、四种查询只换两处；左闭右开与 STL / 多数题解一致，迁移成本低。无论哪套，自检口诀都一样：循环不变量是什么、每轮区间是否真的缩小、终止时答案落在哪个端点。

4 · 二分答案：把二分用在「单调谓词」上

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

经典例子是整数平方根 (LeetCode 69): 求最大的 x 使 $x^2 <= N$ 。判定 $f(x) = (x^2 <= N)$ 显然单调：x 越大越难成立，真值序列形如 $true\dots true false\dots false$ 。于是「最后一个使 f 为真的 x」就是答案——正是四种查询里的「最后一个 ≤」。下面把候选答案 x 摊在纸带上（格内是 $x^2$ ）, 红 = f(x) 成立 (x² ≤ N), 蓝 = 不成立，二分逐步逼近分界。

默认 N = 12: 候选 $x \in [0, 12]$ ，答案是最后一个红 = 3（因 ${3^2 = 9 \le 12 < 16 = 4^2}$ ）。关键在于：我们从不真的去开一个长度 N 的数组—— $x^2$ 是用到时当场算的，区间 [0, N] 只是逻辑上的搜索空间。

识别「能二分答案」只看一件事：单调性。 把问题改写成判定句「x 是否可行？」，若可行性随 x 单调（可行的都 ≤ 某阈值，或都 ≥ 某阈值），就能二分那个阈值。把「求最优值」转成「判定某个值是否可行」，是这类题的统一套路：最大化最小值 / 最小化最大值（如「分 k 段使最大段和最小」）、限速可行性（如 LeetCode 875「珂珂吃香蕉」的最小速度）、第 k 小（在值域上二分「≤ mid 的个数是否 ≥ k」）都是它的变体。

复杂度换了个维度。 数组二分是 $O(\log n)$ （n = 元素个数）；二分答案是 $O(\log (值域) \cdot 判定代价)$ ——搜索的是答案的取值范围而非数据规模。本例值域 [0, N]，判定 f 是 $O(1)$ 的一次乘法，故 $O(\log N)$ 。若判定本身要扫一遍数据（如「珂珂吃香蕉」每次 $O(n)$ ），总复杂度就是 $O(n \cdot \log (值域))$ 。

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

和别的系列串起来看： 二分查找也属于双指针 Two Pointer里「左右对撞」的一类——l 与 r 从两端往中间夹。区别在于本系列用开区间 + 循环不变量的视角统一了所有变体；而二分答案的「单调谓词」思路，又是诸多动态规划 / 贪心优化题里把「最优化」转成「可行性判定」的常用手段。