聊到二分查找我面试别人的时候有个固定动作让对方当场手写一个标准二分。你会发现一个特别有意思的现象八成的候选人在写主体逻辑时非常流畅一到边界条件就卡住反复涂改最后交上来一份要么漏元素、要么卡死循环的代码。这个看起来只有十几行的算法真正坑人的地方从来不在“二分”而在那几行关于边界条件的判断。一旦区间语义不统一、收缩方向写反轻则返回错误结果重则程序直接在循环里出不来。这篇总结我就把自己这些年调二分查找边界问题攒下来的经验摊开讲尽量把“为什么错”和“怎么避坑”都说透。1. 二分查找的核心难点区间语义不统一1.1 为什么代码看着简单却总在边界上翻车二分查找的原理一句话就能讲完在一个有序序列里每次取中间位置的元素和目标值比较大了往左收小了往右收直到找到或者区间空掉。道理谁都懂可一旦落到代码上每个人脑子里的“区间长什么样”其实不一样。有人默认左闭右闭有人默认左闭右开还有人默认左开右开。同一个区间用不同的语义去写循环条件、mid更新公式就全都不一样。这里我举个生活化的例子。猜数字游戏范围1到100告诉你“大了”或“小了”。假设猜了50被告知“小了”那么下一轮猜的范围是51到100。这其实就是左闭右闭的直觉左右端点都是可能值答案一定落在 [51, 100] 这个闭区间里。可如果换一种定义你认为右边界表示“不可能是答案的位置”那猜了50发现小了新区间就应该是 [51, 101)101是哨兵不在候选范围内。也就是说代码写错往往不是你逻辑能力不行而是你脑子里的区间语义和代码里的循环结构没有对齐。一旦区间语义不统一就会出现两种典型故障。第一种是漏查本来答案在某个位置上但区间收缩规则把那个位置提前排除掉了。第二种是死循环区间没有严格缩小left和right卡在相邻位置反复横跳。这两种故障本质上都是对“当前区间内到底包含哪些下标”这件事缺乏一个清晰、一致的约定。1.2 区间写法的三种流派与一张对照表我把常用的区间写法归纳为三种左闭右闭 [left, right]、左闭右开 [left, right)、左开右开 (left, right)。很多教学材料只讲前两种但在实际工程和算法题里第三种也有它的用武之地尤其是处理“查找边界”这类变体时。先给一张对照表后面第三部分会有每种写法的完整代码拆解写法初始化循环条件mid取整命中后返回向右收缩向左收缩典型适用场景左闭右闭 [l, r]l0, rn-1l r向下取整return midl mid1r mid-1标准查找最通用左闭右开 [l, r)l0, rnl r向下取整return midl mid1r mid配合迭代器、STL风格左开右开 (l, r)l-1, rnl1 r向下取整return midl midr mid边界变体、旋转数组等看到这张表你可能会发现一个规律左闭右开的向右收缩和左闭右闭一样都是l mid 1但向左收缩却不一样左闭右开是r mid不是r mid - 1。很多人第一次都会在这里出错原因一会儿我会专门解释。2. 死循环的根源收缩规则违反“单调递减”原则2.1 相邻区间测试法三个数字就能测出死循环避免死循环最硬核的检查方法其实很简单——用一个长度为2的区间做推演。假设 left 3, right 4你手写一份代码心里跑一遍看看下一步区间怎么变。以左闭右闭为例mid 3 (4 - 3) / 2 3。如果代码写的是“当目标值在右侧时left mid”新区间变回 [3, 4]和上一轮一模一样这就死循环了。可如果代码写的是“当目标值在右侧时left mid 1”新区间变成 [4, 4]区间缩短了循环一定能往前走。我管这个方法叫“相邻区间测试法”。每次写完二分不要急着提交先拿一个长度为2的数组比如[1, 3]分别测 target 等于左值、右值、中间不存在的值、比两个都小、比两个都大这5种情况。只要这5种情况都能在有限步内结束且结果正确你的二分大概率是稳的。为什么不是测试长度3的数组因为长度3时mid恰好落在中间问题不容易暴露而长度2的区间最能体现取整方向和收缩规则的交互。2.2 谁在悄悄破坏收敛mid取整方向与left mid死循环的本质是区间长度没有严格递减。二分查找每一步都在做同一件事把候选区间切掉一半剩下的部分作为新一轮区间。如果切完之后区间和原来一模一样循环就永远出不去。这里有个隐蔽点mid left (right - left) / 2这个写法里mid是向下取整的。当 left 和 right 相邻时mid 等于 left而不是居中偏右的那个值。一旦你的收缩规则里有left mid这种写法而 mid 又恰好等于 left左边界就原地不动。然后第二轮继续同样的计算继续原地不动死循环就来了。反过来如果你确实需要写left mid在某些变体题里很常见就必须同时把mid改成向上取整mid left (right - left 1) / 2。这样当 left 和 right 相邻时mid 会等于 right赋值后 left 至少前进一位区间保证收缩。请记住一个搭配口诀left mid 必须配向上取整right mid 必须配向下取整。这两个改动是一套的只改一半就是给死循环送人头。还有一种破坏收敛的情况是循环条件用错了。比如左闭右闭的区间里有人在循环里写while (left right)最后却发现漏查了数组最后一个元素。因为当 left right 时循环已经退出了而剩下的那个位置恰恰从来没有被比较过。这不算死循环但一样是边界处理错误逻辑上同样致命。3. 三种区间写法的模板与拆解3.1 左闭右闭 [left, right]最直觉也最容易记左闭右闭是绝大多数人最先接触的写法也是我在普通查找场景里最推荐的一种。直接看模板int binarySearch(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) return mid; else if (nums[mid] target) left mid 1; else right mid - 1; } return -1; }这段代码里每一处都需要解释。首先right nums.size() - 1因为 right 是可能值数组最后一个下标当然可能包含答案所以必须减1。其次循环条件是left right含义是只要区间里至少还有一个元素就继续查找。如果写成left right当 left 和 right 相等时循环退出那个唯一的候选位置就被跳过了属于漏查。再来看收缩规则。当nums[mid] target时说明答案不可能在 mid 位置也不可能在 mid 左边所以left mid 1直接跳过 mid当nums[mid] target时同理right mid - 1。注意这里两个收缩都用了mid ± 1而不是直接赋 mid因为 mid 本身已经比较过了可以安全排除。这也是左闭右闭写法天然防死循环的原因无论走哪个分支新区间都比旧区间至少少一个元素。关于溢出我习惯写mid left (right - left) / 2而不是mid (left right) / 2。当 left 和 right 都很大时两者之和可能超出 int 范围先减再除就安全了。这个细节在普通题里可能用不到但在处理大规模数据时非常重要写进代码里是一种好习惯不费什么成本。3.2 左闭右开 [left, right)贴合迭代器习惯左闭右开在C的标准库里极其常见因为 STL 的迭代器区间就是左闭右开语义begin()指向第一个元素end()指向最后一个元素的下一个位置。int binarySearch(vectorint nums, int target) { int left 0, right nums.size(); while (left right) { int mid left (right - left) / 2; if (nums[mid] target) return mid; else if (nums[mid] target) left mid 1; else right mid; } return -1; }这段代码和左闭右闭最大的区别有三个。一是right nums.size()因为这个右边界是开区间不包含实际值所以不用减1。二是循环条件变成了left right因为当left right时候选区间已经空了不需要再进入循环。三是向左收缩时用了right mid而不是right mid - 1。第三点是最容易踩坑的地方。很多人在左闭右闭里习惯了right mid - 1切换到左闭右开时也照抄结果就出错了。为什么左闭右开必须right mid因为 right 本身不参与候选新区间是[left, right)如果写成right mid - 1那mid - 1这个位置就会重新被包含进候选区间而它根本没被比较过就等于把可能答案又拉回来了。反过来right mid之后mid 作为新的开区间右边界被排除在外而 mid 恰恰已经比较过且不等于 target排除它是正确的。这里有个记忆技巧开区间边界可以直接赋mid闭区间边界必须赋mid±1。右边界是开区间所以right mid左边界是闭区间所以left mid 1。左闭右开写法同样不会死循环当 left 和 right 相邻时mid 等于 left如果走left mid 1分支left 前进一位区间空如果走right mid分支right 后退一位区间也空。两种情况都能正常退出。3.3 左开右开 (left, right)专门为边界变体准备第三种写法可能很多书里都不讲但它在某些二分变体里意外地好用。它的核心思想是left 和 right 都不参与候选只是两个哨兵。int binarySearch(vectorint nums, int target) { int left -1, right nums.size(); while (left 1 right) { int mid left (right - left) / 2; if (nums[mid] target) return mid; else if (nums[mid] target) left mid; else right mid; } return -1; }初始化时 left 设为 -1right 设为 n因为这两个位置不可能是数组元素纯粹用来界定范围。循环条件left 1 right表示只要左右哨兵之间还有至少一个元素就继续循环。收缩规则里可以使用left mid也可以使用right mid看起来好像违反了我前面说的防死循环口诀但仔细看会发现不会出事当 left 和 right 相邻时left 1 right已经不成立了循环直接退出根本不会给 mid 和 left 相等的机会。左开右开的优势在于它把“mid已经比较过”和“区间边界不参与候选”这两件事统一起来了。尤其是做“查找最后一个小于target的元素”这类变体题时用左开右开思路会非常顺畅因为答案往往直接就是 left 或 right不需要额外判断边界。不过对这个写法不熟的人我建议先完全吃透前两种模板再来尝试这个否则容易把自己绕进去。4. 边界类二分变体查找第一个等于、最后一个等于4.1 查找第一个等于target的位置标准二分找到一个相等的值就立刻返回但很多时候我们要的不是“随便一个位置”而是“第一个等于target的位置”比如一个有序数组[1,2,2,2,3]里 target 是2标准二分可能返回下标1或2取决于先碰到哪个而我们需要的是下标1。这种变体的写法和标准二分不同即使nums[mid] target也不能 return要继续向左收缩直到确认左边没有同样的值了。int firstEqual(vectorint nums, int target) { int left 0, right nums.size() - 1, ans -1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { ans mid; right mid - 1; } else { left mid 1; } } if (ans -1 || nums[ans] ! target) return -1; return ans; }这里有个很关键的处理判断条件写成nums[mid] target而不是nums[mid] target。因为只要中间值大于等于 target答案顶多出现在 mid 或 mid 左边于是先把 ans 记成 mid再向左收缩。循环结束后ans 指向第一个大于等于 target 的位置。但 target 不一定存在比如数组全是3要找5循环结束后 ans 会落在数组末尾所以最后必须验证nums[ans] target不是就直接返回 -1。我第一次写这个函数的时候踩过一个很蠢的坑循环里看到nums[mid] target就直接返回了结果遇到连续重复元素永远返回不了第一个。后来养成习惯凡是这类边界查找一律不提前返回答案记录和区间收缩一起做最后统一验证。4.2 查找最后一个等于target的位置与lower_bound查找最后一个等于target的位置思路和上面完全对称int lastEqual(vectorint nums, int target) { int left 0, right nums.size() - 1, ans -1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { ans mid; left mid 1; } else { right mid - 1; } } if (ans -1 || nums[ans] ! target) return -1; return ans; }判断条件变成nums[mid] target命中时先把 ans 记成 mid然后向右收缩找更靠后的等值元素。这个写法和前一节是对偶的第一个等于用最后一个等于用其他结构几乎一模一样。你甚至可以不写这两个函数直接用语言内置的 lower_bound 和 upper_bound 组合出来但理解内部逻辑对应对题目和面试都很有帮助。再补充一个经常一起出现的变体查找第一个大于等于target的位置也就是 lower_bound。写法几乎就是 firstEqual 去掉最后的相等验证int lowerBound(vectorint nums, int target) { int left 0, right nums.size() - 1, ans nums.size(); while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { ans mid; right mid - 1; } else { left mid 1; } } return ans; }注意 ans 的初始值是nums.size()因为 target 可能比数组里所有元素都大此时 lower_bound 的合法返回值就是“末尾哨兵”也就是插入位置在数组最后。这个边界很多人容易漏一漏就直接数组越界。下面用一张表总结这几个变体的核心区别方便对照记忆变体命中时动作继续收缩方向最后验证第一个等于 target记录 ansright mid-1向左需要验证是否真的相等最后一个等于 target记录 ansleft mid1向右需要验证是否真的相等第一个大于等于 target记录 ansright mid-1向左不需要天然合法5. 实操调试二分查找边界排查的完整方法5.1 步进打印与区间收缩检查说再多理论不如直接上调试手段。我的习惯是写二分时先在 while 开头临时加一行打印把每一轮的 left、right、mid、nums[mid] 都打出来。肉眼观察三到五轮区间是不是每次都变小很快就能定位问题。while (left right) { int mid left (right - left) / 2; printf(left%d right%d mid%d val%d\n, left, right, mid, nums[mid]); if (nums[mid] target) return mid; else if (nums[mid] target) left mid 1; else right mid - 1; }如果在输出里看到 left 和 right 连续两轮完全没有变化mid 也一模一样那基本就是死循环入口。这时候不用多想回去看一个地方当前分支是不是把 left 或 right 重新赋回了原值。最常见的就是漏写1或-1比如把left mid 1写成了left mid。如果想要更自动化可以用断言。在收缩逻辑能保证区间至少减少1的前提下循环开头加一个assert(left right); assert(mid left || mid right);当 left right 时只要 mid 不等于 left 或者 mid 不等于 right区间就必然收缩。这个断言能帮你在调试阶段快速抓出破坏收敛的逻辑实测非常有用。当然正式提交前要把这些调试代码删干净。5.2 边界用例集我每次提交前必测的一组数据二分查找的坑绝大部分集中在边界用例上。我给自己整理了一套固定的测试序列每次写完二分不管是什么变体都先在本地把这组数据跑一遍通过后再提交到在线判题系统。这套序列是这样空数组[]查找任意值应该返回 -1 或合法插入位置。单元素数组[5]分别查5、查3、查7覆盖命中、偏小、偏大三种情况。双元素数组[1, 3]查1、查3、查2、查0、查4这是测死循环最关键的用例。重复元素[1, 2, 2, 2, 3]查找第一个2和最后一个2验证变体逻辑。全部相同元素[2, 2, 2, 2]找第一个2、最后一个2、找1、找3边界上最容易迷糊的场景。奇偶长度数组各来一组比如[1, 3, 5]和[1, 3, 5, 7]分别查头、中、尾覆盖不同取整路径。每次跑完这套用例我基本敢拍胸脯说这个二分没有明显的边界问题。在线判题平台上比如PTA里的二分函数题跑挂十次里有八次就是这些用例没覆盖到。尤其双元素数组和全部相同元素的数组是最容易暴露死循环和边界错位的组合。5.3 一个特殊的浮点二分场景整数下标二分有死循环风险浮点数二分反而不用太担心。求平方根这类问题时通常写法是double left 0, right x; while (right - left 1e-7) { double mid left (right - left) / 2; if (mid * mid x) left mid; else right mid; }浮点数连续取值mid不会和left、right产生整数式地“相等”所以循环会自然推进。但要注意精度的选择1e-7这种阈值如果设得太大最后结果精度不够设得太小循环次数会增多但不会死循环。这里真正该防的坑是别用while (left ! right)当浮点数二分的终止条件浮点误差会带来概率性的死循环或不收敛必须用区间长度阈值或者固定迭代次数。6. 二分查找常见错误速查与自查清单6.1 高频错误对照表把这几年的踩坑经历汇总一下我整理了一张高频错误对照表基本覆盖了二分查找里最常见的几类问题现象错误写法后果修正写法死循环左闭右闭中left midleft和right相邻时左边界不动left mid 1死循环left mid且mid向下取整相邻时mid等于left新区间不变改用向上取整mid left (right - left 1) / 2漏查元素左闭右闭中while (left right)最后一个候选位置没比较改为while (left right)结果越界lower_bound 场景里 ans 初值设为 -1target大于所有元素时非法设为nums.size()边界错位左闭右开中right mid - 1mid-1未被检查却重新进入候选区间改为right mid整型溢出mid (left right) / 2left、right很大时求和溢出改为left (right - left) / 2变体误判nums[mid] target时直接返回无法找到第一个/最后一个相等元素先记录ans继续收缩最后验证这张表我建议收藏尤其是面试前翻一遍基本能避开大多数人都会踩的坑。6.2 提交前最后一遍自查逻辑写完一个二分提交前我会在心里快速过一遍这四个问题第一个问题循环终止时区间是空的还是剩下一个元素我是否明确知道那个未处理位置的下标是什么如果用的是left right循环结束后 left 大于 right区间确实空了如果用的是left right循环结束后 left 等于 right剩下的那个位置是否已经被验证过第二个问题在区间长度为2时mid 到底等于左侧还是右侧我当前的收缩规则和取整方向搭配对不对如果用了left mid检查是否同时改成了向上取整。第三个问题会不会有一个位置被重复搜索或者有一个位置被永久跳过左闭右闭里同时出现left mid和right mid时特别容易卡死左闭右开里出现right mid - 1时特别容易丢元素。第四个问题循环结束后的返回值是否需要附加验证查找是否存在时直接返回 -1 或者 false查找边界时不能假定 left/right 就一定是答案尤其涉及 target 不存在的情况。按这四个问题自查一遍表面上只花一两分钟但能挡住大多数 OJ 上的提交失败。我自己现在写二分习惯性会顺手把边界测试用例也在脑子里跑一遍哪怕只是快速过一下双元素和全部相同元素这两种情况。说白了二分查找的代码面只有十几行真正考基本功的就是那四个地方初始化、循环条件、mid取整方向、区间收缩规则。把它们当成一套固定的模板去用每次只改模板里的判断逻辑比每回临场从头推导要靠谱得多。