Algorithm · Binary Search
"二段性"的艺术：统一模板 · 边界变体 · 二分答案 · 旋转数组 —— 最简单也最容易写错的算法
不是"有序"而是"二段性"——能用一个布尔条件把区间切成两半
边界与死循环：mid 取整方向和收缩语句必须配对
二分答案：把"最小化最大值"翻译成单调可行性的判定问题
Why Binary Search
| 数据规模 | 一个一个看（线性扫描） | 每次砍一半（二分） | 差距 |
|---|---|---|---|
| 1 千条 | 最多 1000 次 | 10 次 | 约 100 倍 |
| 100 万条 | 最多 100 万次 | 20 次 | 约 5 万倍 |
| 10 亿条 | 最多 10 亿次（约 10 秒） | 30 次 | 约 3000 万倍 |
我心里想一个 1–100 的数，你猜，我只回答"大了 / 小了 / 对了"。第一次猜 50，第二次猜 25 或 75……无论我想的是几，7 次之内你一定能猜中。你做对了什么？——你每一猜都把"还有可能"的范围砍掉一半。
如果我改口说"我只告诉你接不接近"——那你就没法判断该往左还是往右，范围砍不掉，只能重来一个个数。二分失效从来不是因为代码写错，而是因为"那一刀"问不出方向。所以做题时先问的永远是：我有没有一个判据能一刀切两半？
Knuth 说过：第一个二分程序 1946 年就发表了，第一个正确的直到 1962 年才出现。16 年栽在三个地方：中点往哪取整、区间能不能真的缩小、边界该不该保留。这三件事必须成套，换一个另外两个要跟着换。
先把"砍一半"写成十行模板 → 用 lower_bound 统一所有边界变体 → 再把同一招用到答案的取值范围上（二分答案）→ 最后看旋转数组这类"看起来不能二分"的题怎么恢复二段性。
Prerequisites & Glossary
| 术语 | 一句话理解（先记住这个，细节后面展开） |
|---|---|
| 二段性 | 存在一个"是 / 否"判据，能把当前区间一刀切成"答案必在的一半"和"答案必不在的一半"。有序只是它最常见的来源 |
| 区间与开闭 | 闭区间 [l, r] 两端都算在内；左闭右开 [l, r) 右端点不算。两套内部自洽即可，但绝不能混用 |
| 中点 mid | 每次拿来"问那一刀"的位置。写成 l+(r-l)/2 而不是 (l+r)/2，防加法溢出 |
| 下取整 / 上取整 | 区间长度是偶数时，中间有两个位置，取靠左还是靠右。取错方向是死循环的唯一来源 |
| 收缩 | 看完 mid 之后，把区间缩小到"答案可能还在的那一半" |
| lower_bound | 第一个 ≥t 的下标；对应的 upper_bound 是第一个 >t 的下标。整个边界家族都由这两个派生 |
| 单调谓词 | 形如 false…false true…true 的布尔函数；sort.Search 找的就是它的第一个 true |
| 二分答案 | 不在数组下标上二分，而是在答案的取值范围上二分（最小速度、最小天数……） |
| 可行性与单调可行性 | "值 v 能不能完成任务"叫可行性；v 可行 ⇒ 更大的 v 也可行，叫单调可行性——它是二分答案成立的唯一前提 |
| 不变量 invariant | 循环过程中始终成立的那句话，比如"答案一定还在 [l, r] 里"。它是判断收缩有没有写对的唯一抓手 |
先读这几篇再回来。本 deck 默认你已经能读懂 O(log n)、数组下标和布尔函数：
复杂度分析 → O(log n) 到底是什么
数组与链表 → 为什么二分依赖"随机访问"
排序算法 → 有序数组是从哪来的
把二分记成一个不断重复的三步动作：① 取中点；② 问一刀（答案在左还是在右）；③ 把区间缩到那一半。后面所有变体（lower_bound、二分答案、旋转数组、找峰值）都不改这个动作，只改"那一刀"怎么问——想清楚判据，代码自然就出来了。
二分最容易写错的地方是"收缩了半天区间其实没变小"。用一句话盯住它就能防死循环：答案一定还在 [l, r] 里。每写一条收缩语句就问一次——这句话还成立吗？区间真的变小了吗？
One Template To Rule Them All
上一页说"每看一眼就砍掉一半"，这一页把它写成十行代码——重点看三件套怎么配对，少配一个就是死循环。
// 闭区间 [l, r] 标准模板 func search(a []int, t int) int { l, r := 0, len(a)-1 for l <= r { // 区间非空 m := l + (r-l)/2 // 下取整 switch { case a[m] == t: return m case a[m] < t: l = m + 1 // t 在右半 default: r = m - 1 // t 在左半 } } return -1 } // 防溢出写法 l+(r-l)/2（C/Java 必备习惯）
① 循环条件 l <= r（闭区间非空）；② 收缩语句 l=m+1 / r=m−1（m 已排除）；③ mid 取整下取整。三者必须自洽——换其中任何一个，另外两个要跟着换。
用"mid 保留"式收缩（l=mid / r=mid）时：若 mid 下取整且走 l=mid，区间 [l,r] 不缩 → 死循环。规则：l=mid 时 mid 必须上取整 (l+r+1)/2。
(l+r)/2 在 32 位语言里 l+r 可能溢出（Java Arrays.binarySearch 历史 bug）。Go 的 int 是 64 位一般不会，但这是跨语言肌肉记忆 + 面试官的检查点。
每次排除一半 → 期望与最坏都是 ⌈log₂n⌉ 次比较（复杂度 deck QA9 的推导）。空间 O(1) 迭代。
Halve · Check · Shrink
Lower Bound · Upper Bound
// lower_bound：第一个 >= t 的下标 func lowerBound(a []int, t int) int { l, r := 0, len(a) // 左闭右开 for l < r { m := l + (r-l)/2 if a[m] < t { l = m + 1 // [m+1, r) } else { r = m // m 可能是答案，保留 } } return l // 不存在时 = len(a) }
① 第一个 ≥ t：lowerBound(a,t)；② 第一个 > t：lowerBound(a,t+1)（整数）或 upper_bound；③ 最后一个 < t：①的答案 −1；④ 最后一个 ≤ t：②的答案 −1；⑤ t 出现次数：② − ①。
循环条件 l < r（开区间不空当）；r=m（m 在开区间外、但可能是答案所以保留）；l=m+1（m 已确认太小）。与闭区间模板不同但内部自洽——别混用两套。
① 空数组返回什么？② 全部小于 t 时返回 len？③ 全部大于 t 时返回 0？④ 重复元素取第一个？——四个 case 手推一遍，边界题就稳了。
LC 34 搜索范围 = 两次 lower_bound（≥t 和 ≥t+1）；LC 35 插入位置 = lower_bound 本身。
Go Stdlib · Monotone Predicate
// sort.Search(n, f)：返回最小的 // i ∈ [0,n] 使 f(i)==true（f 单调） // 例：有序数组中找 target idx := sort.Search(len(a), func(i int) bool { return a[i] >= target }) // idx == len(a) 表示不存在 // 例：找第一个 > 100 的下标 i := sort.Search(len(a), func(i int) bool { return a[i] > 100 }) // 二分答案：速度 v 是否 k 小时吃完 ok := sort.Search(maxSpeed, func(v int) bool { return hours(v) <= h })
把"在有序数组里找值"泛化成"在单调布尔函数上找第一个 true"——数组、答案空间、判定函数统一成一个 API。手写二分的边界错误在这里不存在（标准库写好了）。
f 必须形如 false…false true…true——这正是"二段性"的函数化表达。f 不单调时结果未定义（不报错，坑）。
都是 Search 的特化：SearchInts(a, x) = 第一个 ≥ x 的下标（即 lower_bound）；返回 len(a) 表示所有元素都小。
需要"第一个 true 的同时拿 mid 做别的事"、区间收缩方向非标准、或性能敏感的 hot loop——手写时回到第 2 页模板和配对规则。
Binary Search On Answer
① 问的是"最小的最大 / 最大的最小 / 最少需要多少"；② 存在一个单调可行性：x 可行 ⇒ x+1 也可行（或反之）。两条件齐 → 对"答案本身"二分。
速度 v 越大吃得越快（单调！）→ 判定 hours(v) ≤ H 是否成立 O(n) → 对 v ∈ [1, max(piles)] 二分，总 O(n log maxP)。直接枚举 v 是 O(n·maxP) 爆炸。
"最大和最小化"：上限 cap 越大越容易切 ≤m 段（单调）→ 判定 = 贪心数段 O(n) → 二分 cap ∈ [max(a), sum(a)]。
DP 要设计状态（往往 n²）；二分答案 = log(值域) × O(n) 判定——把指数/平方的组合问题压成对数×线性。先问"答案有没有单调性"再想 DP，是解题顺序的优化。
// LC 875：最小吃香蕉速度 func minEatingSpeed(piles []int, h int) int { return sort.Search(1<<62, func(v int) bool { if v == 0 { return false } hours := 0 for _, p := range piles { hours += (p + v - 1) / v // 上取整 } return hours <= h }) } // sort.Search 直接当"最小可行 v"用 // O(n·log(maxP)) —— 判定是 O(n) 的
Rotated Array · LC 33/81/153
旋转后的数组被断点分成两个有序段。任取中点 m，[l..m] 和 [m..r] 必有一个是有序的——用 a[l] <= a[m] 判断左半是否有序，然后看 target 在不在有序段的范围内。
左半有序（a[l]≤a[m]）：target ∈ [a[l],a[m]) → 去左，否则去右；左半无序 → 右半必有序，同理判断。每步仍排除一半，O(log n) 成立。
a[m] > a[r] → 最小值在 (m, r]；a[m] < a[r] → 最小值在 [l, m]。关键：跟 a[r] 比，不跟 a[l] 比（跟 a[l] 比在未旋转时会误判）。
a[l]==a[m]==a[r] 时无法判断哪边有序 → l++ r-- 双向收缩（最坏退化 O(n)）。这是 33 的重复版唯一新增逻辑。
旋转族的本质：人为构造判据恢复二段性。"每次比较必须能安全排除一半"——判据失效（重复元素）时退化是必然代价。
| 题目 | 判定条件 |
|---|---|
| 33 搜索（无重复）M | a[l]≤a[m] → 左半有序，查 target 是否在内 |
| 153 最小值 M | a[m]>a[r] → min 在右半；否则在左半（含 m） |
| 81 搜索（重复）M | 三值相等 → l++/r--，最坏 O(n) |
| 154 最小值（重复）H | 同上收缩，均摊 O(log n) 最坏 O(n) |
LeetCode Shortlist
| 考法 | 题目（编号 · 难度） | 要点 |
|---|---|---|
| 裸模板 | 704 二分查找 E · 35 搜索插入位置 E · 34 范围 M | 34 = 两次 lower_bound |
| 旋转数组 | 33 搜索 M · 153 最小值 M · 81/154 重复版 M/H | 哪半有序判据；153 跟 a[r] 比 |
| 二分答案 | 875 吃香蕉 M · 1011 运货 M · 410 分割数组 H | 单调可行性判定；同款三题 |
| 局部极值 | 162 寻找峰值 M · 852 山脉数组 E | a[m]<a[m+1] 定爬坡方向 |
| 序列上二分 | 300 LIS M · 334 递增三元组 M | 300 的 tails+lower_bound 是 O(n log n) |
| 数学化二分 | 69 x 的平方根 E · 50 Pow(x,n) M | 69 是答案域二分最小例 |
Cheat Sheet
// 第一个 >= t 的下标；不存在则返回 len(a) func lowerBound(a []int, t int) int { l, r := 0, len(a) // 右端点开区间 for l < r { // 区间非空 m := l + (r-l)/2 // 下取整，防溢出 if a[m] < t { l = m + 1 // m 太小，排除 } else { r = m // m 可能是答案，保留 } } return l }
| 第一个 ≥ t | lowerBound(a, t) |
| 第一个 > t | lowerBound(a, t+1)（整数）／ upper_bound |
| 最后一个 < t | lowerBound(a, t) - 1 |
| 最后一个 ≤ t | lowerBound(a, t+1) - 1 |
| t 出现次数 | lowerBound(t+1) - lowerBound(t) |
| 要素 | 闭区间 [l, r] | 左闭右开 [l, r) |
|---|---|---|
| r 初值 | len(a)-1 | len(a) |
| 循环条件 | l <= r | l < r |
| 收缩 | l=m+1 / r=m-1 | l=m+1 / r=m |
| mid 取整 | 下取整 | 下取整；l=m 时必须上取整 |
| 找不到时 | 返回 -1 | 返回 l（可等于 len） |
1 · 二段性成立吗？先说清"那一刀"是什么——没判据就别二分（162 峰值、33 旋转都不是有序，但有判据）。
2 · 区间真的在缩小吗？盯住不变量"答案还在 [l,r] 里"；l=m 必须配上取整，否则两个元素时死循环。
3 · 两套区间混用了吗？初始值 / 循环条件 / 收缩语句 / 返回值是一套，混一半必错。
4 · 四个边界 case 过了吗？空数组、全都 < t、全都 > t、有重复元素——手推一遍。
5 · 二分答案的前提验证了吗？必须先说清"v 可行 ⇒ 更大 v 也可行"，否则单调性不成立，二分无意义。
Interview QA · Part 1
先自答，再对照：每题先说出你的答案（哪怕只说关键词），再展开下面那行——卡住的那 30 秒才是真正长记性的部分。
本质是二段性：存在一个判据能把当前区间分成"必然满足/必然不满足"两半。有序只是二段性最常见的来源（峰值 162、旋转 33 都不是全局有序）。
l+r 可能超出 int 范围（Java/32 位 C）。写 l+(r−l)/2。Go int 64 位通常安全，但习惯要统一——面试官看到 (l+r)/2 常会追问。
用 l=mid 收缩但 mid 下取整：当 l=r−1 时 mid 恒等于 l，区间永远不缩。规则：l=mid 必须配 (l+r+1)/2 上取整；r=mid 配下取整。
两套都行但内部必须自洽：闭区间配 l<=r 与 r=m−1；开区间配 l<r 与 r=m。混用必错。lower_bound 系统库语义是左闭右开，建议熟记那套。
第一个 ≥t 的下标；全部元素小于 t 时返回 len(a)。由此派生：upper_bound=lowerBound(t+1)、个数=upper−lower、前驱=lower−1。
f 必须满足 false…false true…true 的单调形。Search 返回第一个 true 的下标；f 不单调时结果未定义且不报错——用它之前先证明单调。
每步把剩余可能性减半：k 步后剩 n/2^k，停机条件 n/2^k≤1 → k=log₂n。对比线性扫描 O(n)——n=10⁹ 时是 30 步 vs 10 亿步。
看 a[m] 与 a[m+1]：上坡 → 右侧必存在峰（到结尾一路升也算）；下坡 → m 或其左侧有峰。判据只需保证"答案在哪一半"，与全局有序无关。
Interview QA · Part 2
先自答，再对照。这一组的重点是"识别"——看到题先自己判断它该不该二分，再对照答案里的信号词。
对"答案本身"二分：信号词是"最小化最大 / 最大化最小 / 最少多少天"，且可行性随答案单调。复杂度 = O(log 值域) × O(n) 判定。
都是"给定上限 → 贪心判定是否可行"：875 数小时、1011 数天数、410 数段数。骨架 = 外层二分答案 + 内层 O(n) 贪心；区别只在判定细节。
两种终止：while(r−l>eps)（精度控制，注意 eps 过小导致死循环）或固定迭代 100 次（2¹⁰⁰ 倍缩小区间，最稳）。浮点无"精确等于"，输出 l 或 r 均可。
tails[i] = 长度 i+1 的递增子序列的最小结尾（单调递增）。每个新元素对 tails 二分替换（lower_bound）——替换不改变其单调性， tails 长度即 LIS 长度。
未旋转（整体有序）时 a[m] 恒 > a[l]，会一直往右走错过最小值 a[0]；跟 a[r] 比则：a[m]>a[r] 断点在右，否则最小在左半（含 m）——两种情形都正确。
标准 lower_bound 语义 → sort.SearchInts / sort.Search；二分答案 → sort.Search 直接当"最小可行值"；非标准收缩（峰值、旋转、三分）→ 手写并过第 2 页检查表。
Related & References
参考来源（本 deck 结论可溯源至下列一手材料）
| CLRS · grep/binary search 章节 · Knuth TAOCP 6.2.1 | 二分的经典表述；Knuth 论 1946-1962 的正确实现历史 |
| go.dev · sort 包文档（Search/SearchInts） | "smallest index i for which f(i) is true"的官方语义 |
| C++ std::lower_bound / upper_bound 语义 | 左闭右开与派生关系的标准出处 |
| LeetCode 704/34/33/153/162/875/410/300 题解 | 六种考法的代表题 |
| oi-wiki.org/basic/binary | 二分与二分答案的中文系统讲解 |