很多人把二分法查找当成“有手就会”的基础题但我在面试和实际刷题中见过太多次翻车现场要么死循环要么数组越界要么目标值明明在数组里却返回 -1。这篇文章不教你背模板而是把二分法解题背后真正决定对错的三个关键点提炼成三条铁律梳理清楚之后再回头写代码你会发现以前那些边界问题其实都是同一类错误。无论你是准备算法面试的在校学生还是工作中需要在有序数据里做快速检索的开发者这篇文章都适合读一读。我会从最基础的区间定义说起逐步过渡到左边界、右边界、二分答案这类变体每一部分都会配上可运行代码和踩坑记录争取让小白也能真正理解二分法查找的原理而不是停留在“记住模板”的层面。1. 为什么要立三条铁律二分法看似简单翻车却最多1.1 二分法的高频与高风险二分法查找几乎是算法面试的标配题目LeetCode 上 704 题就是最基础的二分查找。它代码量极少逻辑看起上来也极其直观每次把搜索区间砍掉一半直到找到目标值。但讽刺的是这道“送分题”却是出错率最高的题目之一。我见过太多人栽在这几个地方while 条件写成 left right 还是 left right 拿不准更新边界时 mid 到底加一还是减一犹豫不决更常见的是一运行就死循环或者访问了 nums[-1]、nums[n] 这类越界下标。这些问题单独看都不难难的是它们在变体题目里会出现得千奇百怪。今天查左边界明天查右边界后天查插入位置同一个模板换个题目就失灵本质上就是因为没理解二分法背后的统一规律。1.2 三条铁律到底是什么我把二分法解题的核心规律收敛成三条每次写代码前先对照一遍能避免绝大多数低级错误区间定义先行动手写循环之前必须先明确搜索区间是左闭右闭还是左闭右开之后所有边界更新、循环终止条件、返回值都要和这个区间定义保持一致。有“二段性”才分半二分法的前提不是“数组有序”而是搜索空间存在一个判定条件能让数据在一侧满足、另一侧不满足。单调有序只是二段性最常见的表现形式。循环不变量与收敛性每次循环开始时答案必须仍然在搜索区间内每次循环结束后区间必须严格收缩。这两个条件同时满足循环才不会漏掉答案也不会死循环。这三条看起来简单但每一条展开都能对应到大量实际代码里的错误。下面逐个拆解。2. 铁律一区间定义先行2.1 左闭右闭与左闭右开两种模板对比先看两段最朴素的二分查找代码它们的目标都一样在有序数组 nums 中找到目标值 target 的下标找不到返回 -1。左闭右闭写法def binary_search(nums, target): left, right 0, len(nums) - 1 # 搜索区间 [left, right]左右都能取到 while left right: # 区间不为空的条件是 left right mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 # mid 及其左侧已排除 else: right mid - 1 # mid 及其右侧已排除 return -1左闭右开写法def binary_search(nums, target): left, right 0, len(nums) # 搜索区间 [left, right)right 本身不参与取用 while left right: # 区间不为空的条件是 left right mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 # mid 及其左侧已排除 else: right mid # mid 作为新的右边界保持右开 return -1两种写法都是正确的关键是要在脑子里清楚闭区间下right 指向的元素仍然在搜索范围内所以当 left right 时区间里还有一个元素没有检查循环不能停开区间下right 指向的元素不在搜索范围内所以 left right 时区间已经为空循环可以停。这里我强烈建议初学者先选定一种写法并长期使用不要今天用闭区间明天用开区间。我在刷题阶段曾经过于追求“不同题型用不同模板”结果把自己绕晕了。后来固定用左闭右开所有变体统一处理正确率显著提升。2.2 为什么边界更新不能凭感觉核心推导边界更新是所有二分法学习中最容易糊涂的地方。很多人死记硬背“左边加一、右边减一”却不知道为什么。其实推导非常直接每次比较完 nums[mid] 与 target 后你已经知道了 mid 位置不可能是答案而且基于有序性mid 一侧的所有元素也可以一并排除。拿 [1, 3, 5, 7, 9]target7 举例。左闭右闭写法下初始 left0right4mid2nums[2]5 7说明下标 0 到 2 全部小于 target不可能有目标值所以 left 直接跳到 mid13。接着 left3right4mid3nums[3]7命中返回 3。左闭右开写法下初始 left0right5mid2nums[2]5 7同样排除 0 到 2left3。然后 left3right5mid4nums[4]9 7。注意这里 target 可能在 3 或 4 的位置但下标 4 已经被证明大于 target真正需要保留的是 [3, 4) 这个区间所以 right4。接着 left3right4mid3nums[3]7命中。看到关键了吗闭区间下nums[mid] target 时mid 已经被排除新的右边界应该是 mid-1开区间下虽然 mid 也被排除了但因为 right 本身不参与取用所以把 right 设为 mid 就相当于把 mid 从区间中剔除。2.3 区间不一致带来的典型问题混用区间定义是新手最容易犯的错误典型症状如下闭区间模板里把 while 写成 left right。这样一来当 left 和 right 相等时循环提前退出如果 target 恰好位于这个位置就没有机会检查了。开区间模板里把更新写成 left mid。当区间宽度为 2 时mid 会落在 left 位置left 更新后不变直接死循环。闭区间更新 right mid。由于闭区间里 right 本身可取right mid 会把已经确定的非答案元素保留在区间中不仅浪费一轮循环还可能在特定场景下永远无法收窄。我的建议是把区间定义用注释写在 while 之前。例如# [left, right)然后问自己三个问题循环终止条件对吗left 更新会排除已经判断过的小区域吗right 更新会让中间那一个元素从区间里消失还是被保留3. 铁律二有“二段性”才分半3.1 从有序数组到二段性很多人学二分法时记住的前提是“数组必须有序”。这个说法没错但格局小了。真正让二分法成立的东西是搜索空间具备二段性存在一个判定条件可以从某个分界点开始一侧全部满足另一侧全部不满足。有序数组查值为什么能二分因为“nums[i] target”这个性质在数组下标上是有序变化的。前半段可能都小于 target后半段都大于或等于 target中间只有一个转折点。二分法每走一步都在接近这个转折点所以效率是 O(log n)。工作中你会遇到更多二段性的场景最典型的就是“二分答案”。比如在 n 根绳子里切出 m 根等长绳子问最长能切多长。这个问题看似和“查找”无关但如果你把答案可能取的绳子长度 x 作为搜索空间判定条件 check(x) “能否切出 m 根长度至少为 x 的绳子”这个条件显然随着 x 增大而越来越难成立正好构成二段性。于是长度区间就可以二分。3.2 题目中的几种常见二段性形态我在刷题中总结出以下常见的二段性形态场景判定条件分界点含义有序数组查值nums[mid] 与 target 比较target 所在位置查找第一个 target 的位置nums[mid] target第一个满足条件的位置查找最后一个 target 的位置nums[mid] target第一个大于 target 的位置之前旋转数组找最小值nums[mid] 与 nums[right] 比较左升段与右升段的交界二分答案可行性判定check(mid) 是否成立可行与不可行的边界山峰数组找峰值nums[mid] nums[mid 1]峰顶位置左右两侧的下降趋势举个例子旋转数组找最小值。假设数组是 [4, 5, 6, 7, 0, 1, 2]它由两段升序组成前段所有元素都比后段大。比较 nums[mid] 和 nums[right]如果 nums[mid] nums[right]说明 mid 在前段最小值一定在 mid 右侧于是 left mid 1否则 mid 在后段最小值在 mid 或 mid 左侧于是 right mid。这里依赖的同样是二段性。3.3 如何判断一道题能不能用二分拿到一道题不要先急着看数据范围先问自己能不能写出一个判定函数 f(index)使得 index 从小到大扫过时f 的取值只会从 False 变成 True或者只会从 True 变成 False并且只变化一次如果答案是能那么这道题就可以用二分法。这里不需要要求数据是数值升序也不需要要求数组严格有序只要满足二段性即可。判定函数可以是 nums[mid] 和 target 的大小比较也可以是一个独立的 check 函数。这种方式非常有价值因为它把二分法从“有序数组专用技巧”扩展成了“单调可行性判定通用方法”。处理最大值最小化、最小值最大化这类优化题时这个思路几乎是标配。4. 铁律三循环不变量与收敛性4.1 循环不变量的通俗理解“循环不变量”是计算机科学里比较抽象的一个词但可以用一个生活例子讲明白想象你在一个长廊里找一盏灯你每走一步都会确定一部分区域不可能有灯然后把搜索范围缩小到剩下的走廊里。整个过程中你始终确信“灯就在我当前的搜索范围内”这就是循环不变量。投射到二分法里每次进入 while 循环时答案一定还停留在当前的 [left, right] 或 [left, right) 区间里。而你每次更新 left 或 right 时都基于一个已经完成的判断这个区域已经被证明不可能包含答案所以可以放心排除。只要这种排除是正确循环结束时剩下来的位置就是答案所在。4.2 死循环的根源与 mid 的取整方向死循环几乎是二分法新人必遇的问题根源只有一个某一次循环结束后left 和 right 竟然完全没有变化。最常见的情况发生在区间宽度为 2 时。假设当前 left 2right 3mid 向下取整得到 2。如果某一个分支里执行了 left mid那么新的 left 还是 2区间没有收缩下一次循环还是同样的局面于是死循环。避免死循环要从 mid 的取整方向和更新方式同时下手当代码逻辑需要把 mid 保留为新的 right 时例如 right midmid 取不取整无所谓因为 right 最多收缩到 mid而 mid right向下取整时或 mid right向上取整时都能让区间变小。当代码逻辑需要把 mid 保留为新的 left 时例如 left mid向下取整就是陷阱因为 mid 可能等于 left。这时候要么改用向上取整的 mid left (right - left 1) // 2要么重新调整分支把情况改成可以安全 left mid 1 的形式。我自己的做法是尽量少用 left mid 这种写法想办法把判定条件翻转让 left 的更新总是 mid 1。这样 mid 的取整方向就统一向下不用额外记“什么时候向上取整”心智负担小很多。4.3 自检方法循环必然收敛的验证每次写完二分循环我都会在草稿纸上速算一遍“最危险”的情况区间宽度为 2 时left 和 right 的下一轮值是什么。只要发现 left 和 right 有可能原封不动进入下一轮就说明代码有死循环风险必须修改。另一个更实用的自检技巧是在函数入口处打印或脑补每一轮 left、right、mid 的变化轨迹。通常跑三到五轮就能看出边界有没有问题。当你对三组测试用例都能正常收敛时死循环的概率就大大降低了。5. 三种高频模板查找、左边界、右边界5.1 模板一标准二分查找标准查找的目标找到任意一个等于 target 的下标找不到返回 -1。def binary_search(nums, target): left, right 0, len(nums) # [left, right) while left right: mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid return -1这个模板我建议配合“要插入的位置”来理解循环结束时left 指向第一个 target 的位置。如果 nums[left] target说明命中了直接返回否则 target 不在数组中。标准查找和 lower_bound 本质上是同一件事。5.2 模板二查找左边界lower_bound目标返回第一个大于等于 target 的下标。如果数组中不存在 target返回第一个大于 target 的位置或者 len(nums)表示所有元素都小于 target。def lower_bound(nums, target): left, right 0, len(nums) # [left, right) while left right: mid left (right - left) // 2 if nums[mid] target: left mid 1 else: right mid return left这个模板的核心分支是当 nums[mid] target 时说明 mid 可能是答案也可能答案在 mid 左侧所以不能排除 mid应该让 right mid。当 nums[mid] target 时mid 及左侧全部小于 target不可能成为第一个 target 的位置所以 left mid 1。5.3 模板三查找右边界upper_bound目标返回最后一个小于等于 target 的下标。如果所有元素都大于 target返回 -1。简单实现方式是先找第一个大于 target 的位置再减 1def upper_bound(nums, target): left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: left mid 1 else: right mid return left - 1这里把 nums[mid] target 视为“可以跳过”的情况left 继续向右移动遇到 nums[mid] target 则收缩 right。循环结束后 left 是第一个大于 target 的位置减去 1 就是最后一个小于等于 target 的位置。5.4 模板速查表与适用场景需求使用的模板返回结果精确查找 targetlower_bound 后检查 nums[pos] target下标或 -1查找第一个 targetlower_bound下标查找最后一个 targetupper_boundleft - 1下标或 -1排序数组插入位置lower_bound应插入的下标统计 target 出现次数upper_bound 结果 - lower_bound 结果次数这些模板统一使用左闭右开区间mid 一律向下取整left 更新一律是 mid 1只有 right 的更新根据语义决定是 mid 还是 mid - 1。一旦固定了这套体系从标准查找迁移到边界查找会非常顺滑。6. 从理论到实践拿到题目的五步思考法6.1 五步法我总结了五步思考法每次遇到疑似二分题都会按这个顺序走一遍找判定函数想清楚 f(mid) 是什么是 nums[mid] 与 target 的大小比较还是某个 check 函数。定搜索区间答案可能落在哪个范围内是数组下标范围还是答案数值范围选模板目标是“精确命中”“第一个满足条件”还是“最后一个满足条件”选择对应模板。推循环结束语义循环结束后 left/right 指向什么是否需要进一步的边界判断。补边界条件数组为空、目标小于所有元素、目标大于所有元素、有重复元素时结果是否符合预期。这五步每一步都很简单但连在一起能覆盖绝大多数二分题目的思考过程。6.2 四道经典题目走一遍用 LeetCode 上几道经典题做演示你会发现它们本质上是同一个模板的变体。704 二分查找直接使用 5.1 的标准模板不再赘述。35 搜索插入位置题目要求找到一个位置如果 target 存在返回下标否则返回按顺序插入的下标。这正是 lower_bound 的定义直接写def searchInsert(nums, target): left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: left mid 1 else: right mid return left34 在排序数组中查找元素的第一个和最后一个位置先用 lower_bound 找第一个等于 target 的位置再用 upper_bound 找最后一个等于 target 的位置def searchRange(nums, target): left_pos lower_bound(nums, target) if left_pos len(nums) or nums[left_pos] ! target: return [-1, -1] right_pos upper_bound(nums, target) return [left_pos, right_pos]69 x 的平方根需要在 [0, x] 中找最大的 y使得 y * y x。这是“最后一个满足条件的位置”本质上可以用改写 upper_bound 的思路def mySqrt(x): left, right 0, x 1 # 搜索 [0, x] while left right: mid left (right - left) // 2 if mid * mid x: left mid 1 else: right mid return left - 1这里搜索区间是整数值本身不是数组下标但思路完全一致。6.3 实操避坑清单问题原因解决死循环left 更新为 mid区间不收缩改用 mid 1 或向上取整越界访问 nums[n]循环结束后 left n 还继续取值先判断 left len(nums)返回错误插入位置把 upper_bound 和 lower_bound 搞混先明确要找“第一个大于”还是“第一个大于等于”大整数溢出用 mid (left right) // 2改为 mid left (right - left) // 2重复元素时定位错误标准查找返回任意一个不是边界换 lower_bound / upper_bound最后分享一个我自己的习惯所有二分题写完后至少跑五个用例——目标在数组开头、数组结尾、数组中间、目标小于所有元素、目标大于所有元素。如果这五种情况都通过基本可以放心提交。二分法的 bug 往往不是逻辑有多难而是你总觉得自己“这次肯定没问题”结果边界用例一跑就现原形。7. 写在最后我的二分法自检习惯我个人在实际操作中的体会是二分法最大的敌人不是复杂度而是“以为会了之后就不再检查”。哪怕到现在我写完二分代码依然会手动模拟一轮最坏情况下的区间变化。这个习惯帮我省下了大量调试时间也让我在面对面试官追问边界条件时更有底气。最后再分享一个小技巧如果你在代码里看到自己写了 left mid 或者 right mid立刻停下来问一句“mid 会不会和 left 或 right 相等”。如果答案是会那这一轮循环就没有起到收缩作用必须调整取整方向或改成 mid 1 的形式。这个检查可以做出口诀——凡是 mid 被保留进新区间的分支都必须确保区间宽度确实变小了否则死循环一定在某个角落等你。二分法从理解到实践最关键的转变就是不再把各种模板当作孤立的套路死记硬背而是真正掌握区间定义、二段性、循环不变量这三条铁律。掌握了它们你面对的就不只是 LeetCode 上那几道题而是整整一类“在单调空间里快速定位”的问题。