二分法三大铁律：区间定义、区间收缩与目标判定

聊到二分法我第一个想到的不是教科书上的三行伪代码而是自己在一次笔试里翻车的经历。题目很简单在有序数组里找一个目标值的下标。我五分钟写完一跑测试用例单元素数组直接返回 -1 而不是 0捣鼓半天没想通问题出在哪。后来我把二分法也就是大家常说的二分法查找、折半查找所有踩坑经历整理了一遍发现翻车基本都逃不开三个原因搜索区间定义不清楚、循环里区间没有真正缩小、没想清楚自己要找的到底是值还是边界。这篇就围绕这三条铁律展开从理解到实践把二分法一次讲透。适合刚学算法的同学也适合刷题一段时间但边界条件仍然全凭运气的朋友。1. 二分法到底在解决什么问题1.1 一次真实的翻车现场先说我那次翻车。当时我在写“找有序数组中第一个大于等于 target 的位置”要求返回下标。我用了很常见的写法闭区间while left right然后if nums[mid] target: left mid 1否则right mid - 1最后返回 left。单独跑几个用例像nums [1, 3, 5, 7], target 4返回 2看起来没问题。可一旦遇到target比数组里所有元素都大比如nums [1, 3]target 9我的代码返回 2这个结果恰好也是正确答案。但如果题目改一下要求“target 不存在时返回 -1”这段代码就彻底失灵了你不知道最后那个 left 到底是“插入位置”还是“命中的下标”。问题就出在我从头到尾没有定义清楚 right 的语义也没想明白自己找的是“值”还是“位置”。那次之后我悟到一个道理二分法的代码不是核心核心是思路。代码写错往往是思路里对“区间”“目标”这几个词含糊。所以这篇文章不讲玄学直接给一条能落地的思考链路。1.2 二分法的数学本质不是“有序”而是“单调”如果把二分法单纯理解成“在有序数组里二分查找”格局就小了。它真正的数学前提是存在一个可以在区间上判断的单调条件。比如数组[1, 3, 5, 7, 9]找 5 的下标我们其实是在判断nums[mid] 5这个布尔条件从左到右依次是true, true, false, false, false——它在一个点上从 true 翻转到 false。二分法要做的就是快速找到这个翻转点。理解到这一层很多变种题就通了。为什么“二分答案”也能用二分因为答案的可行性函数是单调的如果 mid 可行那么所有比 mid 大的值也可行如果 mid 不可行所有比 mid 小的值也不可行。这本质上还是在单调序列上做排除。所以有序数组只是“单调性”的一个特例“判定条件单调”才是二分法真正的适用场景。1.3 三大应用类型对应不同的思考方式我平时把二分题目分成三类每一类的思考重心不一样。直接查找目标值是否存在存在返回下标不存在返回 -1代表题是 LeetCode 704。边界查找找第一个满足条件的位置或者最后一个满足条件的位置代表题是 LeetCode 35、34、278。二分答案答案的取值范围是连续的每次猜一个 mid用 check(mid) 判断够不够代表题是 LeetCode 69、1011。三条铁律对这三类都管用只是第三类题目里“数组”变成“答案区间”“元素比较”变成“可行性判断”。后面我会用一道二分答案题演示怎么对接。2. 铁律一搜索区间定义先行全程不许变卦2.1 两种常用区间左闭右闭 VS 左闭右开写二分法之前第一件事是问自己left 和 right 构成的区间是闭的还是开的最常用的两种左闭右闭[left, right]left、right 都指向可能包含答案的数组元素。初始化left 0, right len(nums) - 1。左闭右开[left, right)left 指向可能包含答案的位置right 指向“第一个不可能包含答案”的位置。初始化left 0, right len(nums)。闭区间很好理解大部分人学算法都从它开始。开区间的好处有两个一是当答案可能出现“数组末尾之后”时right len(nums)天然合法不用特殊处理二是区间本身就是空的定义很干净left right时就表示没东西可找了。这不是风格问题而是数学语义问题。你选了闭区间所有的边界收缩公式就从闭区间推导选了开区间公式就变成另一套。最怕的就是一会儿闭一会儿开代码写出来四不像。2.2 区间定义直接推导出 while 条件和边界更新很多人背模板一换条件就懵。其实不用背只要记住一个推导原则每次移动边界都问自己一句“mid 这个位置还有可能是答案吗”。在闭区间[left, right]里如果nums[mid] target答案不可能在 mid 及右边所以right mid - 1。如果nums[mid] target答案不可能在 mid 及左边所以left mid 1。因为left right时还有一个元素没检查所以循环条件用while left right。在开区间[left, right)里如果nums[mid] target答案在[left, mid)所以right mid。这里不会丢元素因为 right 本身不参与比较mid 还能在下一轮被检查。如果nums[mid] target答案在[mid 1, right)所以left mid 1。因为left right时区间已经为空没有未检查元素所以循环条件用while left right。看出区别没有闭区间因为左右都包含移动边界时必须mid ± 1开区间因为右边界不包含向右缩时可以保留 mid向左缩时可以直接right mid。只要从定义出发任何一行代码都能验证对错。2.3 同一道题两种区间写法对比用 LeetCode 704 在有序数组里查找目标值写两种都能跑的版本。闭区间写法def search(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid - 1 return -1开区间写法def search(nums, target): left, right 0, len(nums) 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两种都对。闭区间版本如果写成right mid可能死循环开区间版本如果写成right mid - 1可能跳过目标值。所以铁律一的核心不是选哪种而是选了哪种就严格执行哪种边界更新公式不能混搭。2.4 实操习惯代码里先注释区间我后来养成了一个习惯写二分前先在两行注释里写清楚区间语义再动代码。# [left, right]左右都包含答案 # 循环条件 left right收缩用 mid /- 1或# [left, right)right 不包含答案 # 循环条件 left right收缩用 mid / mid 1这两个注释写出来思路就顺了。面试里这个动作也很加分说明你不是在背模板而是真的有建模意识。我在带新人时发现让他们先写注释边界错误率至少降一半。3. 铁律二区间必须收缩绝不原地踏步3.1 死循环的本质区间没有变小二分法死循环只有一个原因某次循环结束后left 和 right 跟进入循环前完全一样下一轮又重复上一轮的一切。最常见的触发代码长这样while left right: mid (left right) // 2 if nums[mid] target: left mid else: right mid假设现在left 3, right 4下取整得到mid 3。如果条件成立执行left 3left 根本没变下一轮还是left 3, right 4死循环。为什么会发生这种情况因为下取整的 mid 在区间只剩两个元素时永远等于 left。此时只要代码里有“保留 mid”的收缩动作比如left mid就会原地踏步。相反right mid在下取整时是安全的因为当right left时mid一定小于right所以right mid至少让 right 变小了。3.2 上取整与下取整其实是收缩策略的一部分很多人以为 mid 取整只是个计算细节其实它是收缩策略的一部分。要不要用上取整取决于你有没有“保留 mid 向右缩”的动作。我用一张表总结写代码前对一下基本不会错收缩动作场景mid 取整方向left mid 1确定 mid 不是答案向右缩下取整right mid - 1确定 mid 不是答案向左缩下取整left midmid 可能是答案向右保留必须上取整right midmid 可能是答案向左保留下取整表里最关键的一条是只要出现left midmid 就必须上取整也就是mid left (right - left 1) // 2。这样当left 1 right时mid right无论条件成立与否区间都能缩小。我用这个表检查过几十道题每次都能提前发现死循环隐患。3.3 “排除”和“保留”两种视角边界更新可以分为两类动作排除 mid 和保留 mid。排除 mid 是说你已经确定 mid 这个位置绝对不可能是答案所以可以放心地把区间跨过它。比如在升序数组里找第一个大于等于 target 的位置当nums[mid] target时mid 以及左边全部小于 target都不可能是答案于是left mid 1。保留 mid 是说mid 有可能是答案但你还想继续在它的一侧找更优的位置。比如找最后一个满足条件的位置当nums[mid] target成立时mid 可能是答案但右边可能还有满足条件的位置所以left mid继续往右试探。每次写收缩语句时先判断这次到底是排除还是保留然后对照表格选取整方向。可以说铁律二就一句话区间必须严格缩小任何让 left 或 right 等于 mid 且 mid 等于旧值的写法都是死路。4. 铁律三先定目标再定收缩方向4.1 三种目标精确值、左边界、右边界同一道题目标类型不同代码差别很大。我把它们分别叫精确查找、左边界查找、右边界查找。精确查找最简单nums[mid] target时直接返回 mid不等就继续缩。它的循环体里有一个“出口”所以死循环风险低。左边界查找是找“第一个满足条件的位置”典型就是找第一个大于等于 target 的下标。关键点是即使nums[mid] target也不能直接返回因为左边可能还有相同的元素。正确做法是让 right 继续向左压最终 left 停在第一个满足条件的位置。右边界查找是找“最后一个满足条件的位置”比如找最后一个小于等于 target 的下标。反过来即使nums[mid] target也不能返回因为右边可能有更多满足条件的元素。正确做法是让 left 继续向右推最终 right 停在最后一个满足条件的位置。4.2 一张表记住三个模板我把自己常用的三个模板整理成了对比表场景循环条件mid 取整满足条件时怎么缩返回值精确查找left right下取整直接 return midmid 或 -1左边界left right下取整right midleft右边界left right上取整left midright这张表我用了很久。每次做题先判断属于哪一类然后直接把对应的条件、取整方式、收缩动作填进去最后再根据题目微调返回值正确率会高很多。4.3 统一视角找“第一个”还是“最后一个”满足条件的位置如果觉得三类模板还是有点多我再给一个更统一的思考方式把数组看成被一个布尔条件分成前后两段前段不满足后段满足。二分法就是在找这个分界点。找左边界本质上就是找第一个满足条件的位置。找右边界本质上就是找最后一个满足条件的位置。两个边界之间的距离就覆盖了所有满足条件的区间。我在实际做题时都会先在心里把布尔条件写出来。比如“搜索插入位置”布尔条件是nums[i] target答案是第一个 True 的位置“x 的平方根”布尔条件是mid * mid x答案是最后一个 True 的位置。一旦能写出这个条件模板就能精确匹配零犹豫。4.4 怎么快速判断题目属于哪一类一个很实用的判断方法看题目问的是下标、插入位置还是一个数值答案。如果问“下标是否存在”大概率是精确查找。如果问“第一个/最左边的位置”“插入位置”“第一个错误的版本”这类就是左边界查找。如果问“最后一个/最右边的位置”“最多能装多少”“最大可行值”就是右边界查找。如果题目给你一个 check 函数让你在答案区间上二分那多半是二分答案它内部的收缩方向依然看 check(mid) 的真假。这部分我放到实操里用一道题展开。5. 从理解到实践三道经典题完整走一遍5.1 例一LeetCode 704 二分查找精确查找题目是标准的精确查找升序数组找 target找到返回下标找不到返回 -1。我用闭区间版本跑一遍完整推演def search(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid - 1 return -1拿nums [1, 2, 3, 4, 5], target 4走一遍初始left0, right4mid2nums[2]3 4left3mid3nums[3]4返回 3。没问题。再看三个边界用例空数组直接返回 -1单元素数组[5]找 5left0, right0循环条件成立mid0命中单元素数组找 6left0, right0nums[0]5 6left1循环结束返回 -1。单元素数组就是最容易暴露 while 条件写错的用例建议每次都先拿它试。5.2 例二LeetCode 35 搜索插入位置左边界这题要求返回 target 在有序数组中的下标如果不存在返回它应该被插入的位置。其实就是在找“第一个大于等于 target 的位置”。我用左闭右开模板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 left注意 right 初始值是len(nums)不是len(nums) - 1。为什么因为插入位置可能等于数组长度。比如nums [1, 3, 5, 6], target 7答案应该是 4也就是数组末尾之后的位置。如果 right 初始化成len(nums) - 1 3开区间[0, 3)永远覆盖不到下标 4答案就丢了。这是开区间写法最大的优势不用为了“末尾插入”单独写 if。拿nums [1, 3, 5, 6], target 2手动推演left0, right4mid2nums[2]5 2所以right2mid1nums[1]3 2right1mid0nums[0]1 2left1。此时left right 1循环结束返回 1。数组里 2 应该插在 1 和 3 之间下标确实就是 1分毫不差。5.3 例三LeetCode 69 x 的平方根二分答案这题要返回 x 的算术平方根的整数部分也就是最大的整数 mid满足mid * mid x。这是典型的右边界查找不过是在答案区间上做二分而不是在数组上。我用右边界模板def mySqrt(x): if x 2: return x left, right 0, x while left right: mid left (right - left 1) // 2 # 上取整 if mid * mid x: left mid else: right mid - 1 return left这个写法里mid必须上取整因为在left 1 right时如果还下取整mid等于 left而left mid会死循环。上取整后mid等于 right要么left跳到 right 退出要么right收到 mid - 1 退出两边都安全。手动验证x 8left0, right8mid416 8right3mid24 8left2mid39 8right2。此时left right 2返回 2。8 的算术平方根是 2.828取整确实是 2。这道题还有一个容易踩的点在 C / Java 里mid * mid可能超过 int 范围要写成long long。Python 没有这问题但面试时要主动提一句能加分。6. 二分法高频翻车点诊断与修复实录6.1 死循环定位法遇到死循环第一反应不是瞎改代码而是加打印。我一般会在循环里临时加一行print(left, right, mid)然后看输出里有没有重复状态。如果某一轮的 left、right、mid 和上一轮一模一样说明收缩语句没生效。对照铁律二查到底是该用上取整却用成了下取整还是代码里出现left mid但 mid 是下取整。定位到具体行问题就解除一半。我自己的经验死循环 90% 出在left mid配下取整。如果你发现自己的代码里同时出现了这两样不用看别的先把 mid 改成上取整。6.2 while 条件写成还是看区间空不空判断标准其实在上面推过闭区间里left right时还剩一个元素没查所以要用开区间里left right表示区间已经为空所以用。如果你用闭区间却写单元素数组就会漏查用开区间却写就可能在区间为空后多进一轮循环大概率越界。我把这个和初始化放一起记闭区间配right len(nums) - 1配开区间配right len(nums)配。三个是一套的不能拆。6.3 初始化 right 的黄金法则不管闭区间还是开区间right 的初始值都要保证“答案一定在搜索范围内”。数组场景里闭区间是len(nums) - 1开区间是len(nums)。二分答案场景right 要么取题目给的上界要么取一个一定可行的值比如求平方根时right x。如果 right 初始值定得太小答案一开始就被排除在搜索范围外面后面写得再对也是白搭。注意求平方根时right x对x 2的情况其实也能跑但单独处理一下更快也避免mid 0时0 * 0 0造成一些不必要的分支。这是小优化不算必要但建议加上。6.4 整数溢出这个经典问题在 C 或 Java 里mid (left right) // 2在 left 和 right 接近INT_MAX时会溢出导致 mid 变成负数。正确写法是mid left (right - left) // 2或者mid left ((right - left) 1)。Python 里整数可以无限大不会踩这个坑但很多面试官会习惯性问一句写 C 的人尤其要注意。6.5 重复元素不用怕但别用精确查找模板套边界题数组里有重复元素时精确查找模板容易让你怀疑人生明明找到了 target但我想要的是最左边那个怎么办别急你要做的是先换目标类型。找左边界就老老实实用左边界模板即使命中也不返回继续right mid找右边界同理命中后继续left mid。只要目标清晰重复元素对二分法没有任何额外难度。6.6 给刷题人的一条训练建议二分法要练到肌肉记忆光看文章没用。我建议按这个顺序刷704 精确查找、35 插入位置、278 第一个错误版本、34 查找区间左右边界、69 平方根、1011 送包裹能力。前五道把三类模板各练两遍第六道体会二分答案的 check 函数思路。刷的时候用我这套流程走先写区间注释再判断目标类型再选模板最后用单元素、双元素、全相同、target 在两端外这几类用例自测。坚持两周二分法基本不会再翻车。我自己到现在还会用这套流程写二分前先注释区间定义再问自己要找的是第一个满足还是最后一个满足最后对照收缩方式检查 mid 取整。这三步走完代码基本一遍过。这大概就是我把“三条铁律”内化之后最直接的变化也希望对你一样有效。