二分查找与变体：边界、旋转与答案空间

一句话定义

二分查找（Binary Search）在单调（有序只是其特例）的搜索空间上每次用一次判定淘汰一半，O(log n)；工程价值不在「查有序数组」，而在「把任何可行性单调的问题转成判定问题后折半答案空间」。

为什么重要

Bentley 的统计：专业程序员写二分，首次正确率不到 10%——边界与不变量是它全部的难点，也是最好的不变量训练场。掌握「左边界/右边界/答案空间二分」三个模板后，你能处理旋转数组、第一个坏版本、最小可满足容量等一大类题，还能读懂 lower_bound/upper_bound 这类标准库语义。

前置知识

kp-002（O(log n)）；数组寻址常识（kp-006）。

核心概念

• 单调性是本质：数组有序 ⇒ 「≥x 的判定」从某处起恒真；一切二分的成立条件都是「答案在某个单调边界上」。
• 循环不变量：半开区间 [l, r) 内待查、l 之外全「否」、r 之外全「是」——写对边界的关键是把不变量说出口。
• 三个模板：①精确查找（l ≤ r，命中返回）；②左边界 lower_bound（第一个 ≥ x）；③右边界 upper_bound（第一个 > x）——②③同构，仅比较符不同。
• mid 防溢出：mid = l + (r − l) / 2。
• 答案空间二分：对「最小满足值 v」在 [lo, hi] 上二分，判定函数 check(v) 需单调（v 越大越可能满足）。
• 收敛细节：整型用 l = mid + 1 / r = mid；浮点用固定次数（如 100 次）或区间长度阈值收敛，避免死循环。

直观类比

翻字典找单词：翻到中间比一次，丢掉一半——但真正的本事是把「找单词」换成「找最小的能承受的载重」「第一个坏掉的版本」：只要「是/否」沿轴单调，折半就合法。

原理与机制

lower_bound（左边界）模板与不变量：

不变量: a[0..l−1] < x 且 a[r..n−1] ≥ x（r 永不指向待定区）
l ← 0; r ← n
当 l < r:
    mid ← l + (r − l) / 2
    若 a[mid] < x: l ← mid + 1
    否则:          r ← mid        // a[mid] ≥ x，mid 可能就是答案，不能丢
返回 l（== r）   // 首个 ≥ x 的下标；l==n 表示不存在

为什么用半开区间：l==r 时机唯一、终止条件无歧义，且「mid 可能是答案时令 r=mid」不会丢解——这正是闭区间写法 [l, r] 最容易出死循环的地方（mid 取整靠左时 r=mid 可能停滞）。

图示

a = [1, 2, 4, 4, 4, 7], 查 x = 4
lower_bound: 第一个 ≥4 的下标 = 2
upper_bound: 第一个 >4 的下标 = 5
⇒ 4 的个数 = upper − lower = 3     （两模板相减即计数）

旋转数组 [4,5,6,7,0,1,2] 找 0:
  判定「mid 在左坡还是右坡」→ 判断目标在哪半 → 折半（O(log n)）

实例或案例

• 标准库语义：C++ lower_bound/upper_bound、Python bisect_left/bisect_right 与本节模板一一对应。
• LeetCode 278 第一个坏版本：答案空间二分的原型题。
• 传输包裹/分分配料（LeetCode 1011/410）：「最小化最大负载」——check(容量) 单调，二分容量 + 贪心 check。
• 旋转数组找最小值/找目标（LeetCode 153/33）：mid 与端点比较定坡向。

常见误区

• 闭区间与半开区间写法混用导致 l=mid 死循环：全文统一一种区间约定并守住不变量。
• mid = (l + r) / 2 在大数组/大整型下溢出：用 l + (r−l)/2。
• 在无单调性的序列上二分（如普通无序数组）：判定不单调，结果无意义。
• 浮点二分用 while l < r：浮点永不严格相等，需改次数/长度收敛条件。
• 忘记「l==n 表示不存在」的出口语义，导致越界访问。

自测题

1. 手写 lower_bound，并口头陈述循环不变量。

答案要点：见机制节模板；不变量「[0,l) 全 < x，[r,n) 全 ≥ x，[l,r) 待定」，终止 l==r 即答案。

1. 在 [1,2,4,4,4,7] 中求 4 的个数，写出用两模板的表达。

答案要点：upper_bound(4) − lower_bound(4) = 5 − 2 = 3。

1. 设计「木材切割求最大长度使段数 ≥ k」的二分方案。

答案要点：答案空间 [1, max]；check(L) = Σ⌊lenᵢ/L⌋ ≥ k 单调递减；求最大满足值用右边界型二分。

与其他知识点的关系

kp-024 的分治是「每次二分 + 两侧都留」的推广；kp-029 的匹配与本题同属「利用单调结构跳过无效区间」；kp-032 的对拍测试常拿暴力线性扫描作为二分的对照实现。

延伸阅读

《编程珠玑》第 4 章（含二分 20 年 bug 史与正确性论证）；Knuth 关于「首个正确的二分到 1962 年才出现」的考证（TAOCP 卷 3，6.2.1 节）。