LeetCode 704. 二分查找：边界与模板的一次性解决

二分为什么「写对很难」

二分查找的思路五岁小孩都能懂：有序数组找目标，砍一半。但 LeetCode 上二分的提交通过率长期只有 50% 上下——难的从来不是思路，是边界的写法：left <= right 还是 left < right？mid = left + (right - left) / 2 还是 mid = (left + right) / 2？更新用 mid ± 1 还是 mid？这些选择不是随机的，是由「区间定义」决定的——搞懂区间不变量，边界题全部一次写对。

区间不变量：一个方法解决所有边界

核心思想：在写循环的每一行时，问自己「我的搜索区间是什么」——区间定义一旦确定，循环条件、更新方式全部自动推导：

模板一：闭区间 [left, right]——「答案可能存在于 [left, right] 的任何位置」——循环条件：left <= right（闭区间含两端，left == right 时区间仍有一个元素，还要判断）——更新：mid 不是目标时，mid 已被检查过，排除——left = mid + 1 或 right = mid - 1（区间收缩到不含 mid）——循环结束时：left = right + 1，区间为空——返回 -1（找不到）。

模板二：左闭右开 [left, right)——「答案可能存在于 [left, right)」——循环条件：left < right（右开，left == right 时区间为空，停止）——更新：left = mid + 1 或 right = mid（mid 本身在开区间外，right = mid 不含 mid）——循环结束时：left = right——这个边界很有用（插入位置、第一个大于等于 target 的位置）。

# 模板一：闭区间，找精确目标
def search(nums, target):
    left, right = 0, len(nums) - 1   # [left, right]
    while left <= right:              # 区间非空
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1            # [mid+1, right]
        else:
            right = mid - 1           # [left, mid-1]
    return -1

graph TD
    A[区间不变量] --> B[闭区间 [l, r]<br/>条件: l <= r<br/>更新: l=mid+1 / r=mid-1<br/>结束: 返回 -1]
    A --> C[左闭右开 [l, r)<br/>条件: l < r<br/>更新: l=mid+1 / r=mid<br/>结束: l 即边界]
    B & C --> D[选一种从头到尾不混用<br/>混用是所有边界 bug 的来源]

「混用」是所有 bug 的来源：一半代码按闭区间写、一半按左闭右开写——while left < right 配 right = mid - 1——区间悄悄丢失元素或死循环——选定一个模板，从头到尾不换——这就是「写对二分」的全部秘密。

变体：二分的真正战场

变体一：找第一个等于 target 的位置（左边界）。数组有重复值——找目标第一次出现的位置——「左边界」的思路：找到目标后不返回，继续向左收缩（right = mid - 1，看左边还有没有）——「收缩到无」时 left 就是左边界——模板二（左闭右开）天然适配：循环结束时 left = right = 第一个 ≥ target 的位置。「第一个 ≥ target」的推广：找第一个大于、最后一个小于——「边界二分」的统一心智：「找第一个满足条件 P 的位置」——条件 P（≥ target、> target、≤ target）——「单调性」是二分的前提：条件 P 在数组上必须「一段真一段假、边界清晰」——「单调性」是二分的本质条件（不是「有序」本身，是「判定条件的单调性」）。

变体二：旋转排序数组（LeetCode 33）。数组在某个点被旋转（[4,5,6,7,0,1,2]）——「部分有序」的二分：mid 把数组分成两半，必有一半是有序的——判断 target 在不在有序的那半（「有序半」的判断：nums[left] <= nums[mid]）——在则收缩到有序半，不在则去另一半——「每次砍掉一半」的性质保住了——旋转数组二分是「二分本质是单调判定」的最佳证明：整体不单调，但「每半至少一半单调」仍然可判。

变体三：答案二分（binary search on answer）。二分不只搜数组——「搜答案本身」：LeetCode 875 爱吃香蕉的珂珂（最小吃香蕉速度 K，使 H 小时内吃完）——「答案空间单调」：速度越快耗时越少——「对每个假想的速度 K，验证可行性 O(n)」——二分答案 K——「验证函数」替代「有序数组」——「答案二分」的应用清单：最小等待时间、最大最小值、最小最大值——「求『最小的满足条件的值』——答案二分是标配工具——这是二分从「数组查找」到「通用优化技术」的跃迁。

二分的进阶：变体家族与「答案二分」的实战

二分查找的进阶：变体家族的系统梳理与「答案二分」的实战应用。「变体家族」的系统化：「第一个 ≥ x」（lower_bound 的语义——「≥ x」的含义（第一个不小于——「第一个 > x」（upper_bound——「第一个 ≤ x」（lower_bound(x+1)-1——「最后一个 < x」（lower_bound(x)-1——「四个变体的推导」（从两个原子推导——「推导式记忆」优于列表背诵——「两个原子」的签名记忆（「lower：≥；upper：>」——「签名差一个等号」——「等号的位置」决定边界。「答案二分」的实战：「答案二分的模板」：「验证函数 check(mid)」（单调的验证——「答案空间的二分」（left=最小可能、right=最大可能——「答案的收敛」（check(mid) 过 → 缩小上界 / 不过 → 提高下界——「收敛的方向」按问题（最小满足/最大满足——「实战 1：爱吃香蕉的珂珂」（LeetCode 875——最小速度 k 使 H 小时吃完——「check(k)」（每堆 ceil 除法求和——「k 的单调性」（速度越大耗时越少——「二分 k」的范围（1 到 max(piles)——「实战 2：分割数组的最大值」（LeetCode 410——最小化最大子数组和——「check(mid)」（贪心切分，段数 ≤ m——「二分的值域」（max(nums) 到 sum(nums)——「下界是 max」（每段至少装最大的——「实战 3：传送带上的包裹」（类似珂珂——「三个实战的共性」：「答案有单调性 + 验证可 O(n)」——「答案二分的适用判据」——「『最大化最小值』『最小化最大值』」的关键词识别——「看到这两个短语，条件反射答案二分」。「二分在工程中的延伸」：「数据库的范围查询」（B+ 树的 lower_bound/upper_bound——「索引的边界查询」——「时间序列的窗口检索」（时序数据库篇——「日志系统的二分」（按时间戳定位日志段——「二分」在存储系统的无处不在——「算法课的 704」到「数据库内核」——「同一个算法」贯穿。二分的进阶总结：变体家族（两个原子的推导式记忆）+答案二分的实战（珂珂/分割/传送带——「最大化最小值」关键词）+工程延伸（B+ 树范围查询、日志定位）——「二分」从「数组里找一个数」进化为「在单调性上求边界」的通用技术——「掌握了单调判定+边界收缩，就掌握了二分的全部」**——剩下的只是「找到判定函数」的题目理解工作。

二分的高频问答：溢出、不变量与答案二分的失效场景

收尾前回答三个高频追问，它们覆盖了二分在面试里九成以上的边界讨论。

问题一：mid = (left + right) / 2 什么时候真的会溢出？——left + right 是先加后除，两个下标都在 32 位有符号整型上限附近时，相加结果超过 2³¹−1 就会翻转变负数——理论上数组长度要上十亿量级才触发，刷题几乎碰不到，但 JDK 的 Arrays.binarySearch 真的在这个写法上藏了多年的溢出 bug（Joshua Bloch 2006 年那篇著名的博客），防御性写法从此成了行业惯例：left + (right - left) / 2 数学上恒等且永不溢出；Java 还有第三种写法 (left + right) >>> 1，用无符号右移把溢出翻负的符号位当数值位处理，同样安全。面试答这道题的关键不是背结论，是说出因果链：加法可能溢出、减法不会、右移分有符号无符号——一句话就能让面试官确认你是理解而不是背诵。Python 的整数无上限，语法上怎么写都不会错，但写法风格要与目标语言的习惯统一——跨语言的人最容易在这里带出错误的肌肉记忆。

问题二：面试官问「为什么这里用 left <= right」，标准回答是什么？——正确姿势是报出区间定义，让边界从定义里长出来：「我的搜索区间是闭区间 [left, right]，left == right 时区间里还剩一个元素没检查，所以条件带等号；如果按左闭右开定义，left == right 时区间已空，条件就不带等号。」追问「循环结束时 left 在哪」也是同一套推导：闭区间下结束时 left = right + 1、区间为空；左闭右开下 left == right，恰好是「第一个不满足条件的位置」——这也是为什么找边界的变体偏好左闭右开模板。这段话术的本质是用不变量回答边界：每一处边界写法都能从区间定义推导，而不是「我背的模板长这样」——能把推导讲清楚的人，换任何变体都不会错；讲不清楚的人，题目换张皮就原形毕露。

问题三：答案二分什么情况下会失效？——两个前提必须同时成立：答案空间对判定函数单调（k 可行则更大的 k 也可行，或反之）与验证能在可接受时间内完成。失效的典型有两类：判定不单调——比如把「分割成 k 段使最大段和最小」改出附加「每段和为奇数」这类离散约束，单调性被破坏，二分会给出貌似合理实则错误的答案；验证本身困难——「能否装满」好验证、「最优装载方案」难构造，此时二分的前提塌了一半。另一个实用细节是浮点答案二分：答案是小数时不能靠整数加减收敛，标准做法是固定迭代次数（比如 100 次，让区间缩小 2¹⁰⁰ 倍）或精度阈值（区间长度小于 eps 即停）——「差一位小数」的 WA 多半出在这里。总结成四步检查清单：先证单调、再证可验证、整数防溢出、浮点控精度——四步过完，答案二分才敢落到代码上。

小结

二分查找的完整体系：区间不变量（闭区间或左闭右开——选定后循环条件与更新自动推导——混用是所有 bug 的来源）；变体的统一心智（「找第一个满足单调条件 P 的位置」——左边界二分的模板二天然适配——单调性是二分的本质条件）；进阶变体（旋转数组的部分单调、答案二分——对答案空间二分、验证函数替代有序数组）；工程细节（mid = left + (right - left) // 2 防溢出——大数相加的溢出——Java/C++ 的必写细节）。给学习者的建议：二分不要背模板，要背「区间不变量」的检查动作——写完每一行，问「此刻我的区间还满足我最初声明的形状吗」——这个动作让所有的边界 bug 在写的时候就现形。

二分查找的错误从来不在「思路」，在「区间的心智模型与代码不一致」——把不变量刻进写代码的每一行，二分就永远是对的。