提到二分查找很多人的第一反应是这题我会。但真上手写的时候尤其在刷题网站上一提交马上原形毕露要么死循环要么越界要么目标值明明存在却返回 -1。我自己带过不少同事也看过大量提交代码发现绝大多数问题根本不是算法思路的问题而是边界规则没有想清楚。左闭右开还是左闭右闭、while 里写还是、left 和 right 到底是加一还是不减一这些细节只要错一个整套代码就废了。这篇文章我把二分查找的边界问题一次性讲透。重点不是让你背一个模板而是理解每一行代码背后的契约知道为什么这么写、什么时候要改、改了会有什么连锁反应。无论你是刚开始学算法的学生还是需要在工程里手写二分的老兵这篇文章都值得静下心读一遍。1. 为什么简单二分总在边界上翻车差一错误的真正根源1.1 大多数人的翻车现场看似正确却死循环的代码先看一段我见过无数次的代码。目标是查 target 在数组中的位置不存在返回 -1int search(vectorint nums, int target) { int left 0, right nums.size(); while (left right) { int mid (left right) / 2; if (nums[mid] target) return mid; else if (nums[mid] target) left mid; else right mid; } return -1; }拿去跑nums [1, 3, 5, 7, 9], target 5正常返回。再跑target 3还是正常。但如果跑target 4程序就死循环了。看到这里你可以先停一下想想死循环是怎么产生的。我直接告诉你答案nums [1, 3, 5, 7, 9]当 left 1、right 2 时mid (12)/2 1nums[1] 3 4于是 left mid 1。区间又变回 [1, 2]mid 还是 1就这样永远转不出来。问题出在left mid这一步当区间只剩下两个元素时mid 正好落在 left 上left 没有前进区间永远不会收缩。这就是典型的边界错误而且非常隐蔽因为大部分测试用例都能跑过。1.2 循环不变量写二分前必须先定下的契约上面这个 bug 的根源是写代码的人没有明确回答一个问题每次循环开始时区间 [left, right] 到底表示什么在二分查找中我们心里必须有一个循环不变量——一个在循环的每次迭代前后都成立的性质。它定义了你对 left 和 right 的语义承诺。常见的有两种区间 [left, right] 内可能包含目标值right 指向的是最后一个仍可能包含目标的元素区间 [left, right) 内可能包含目标值right 指向的是第一个不可能包含目标的元素如果你的循环条件是while (left right)默认你采用的是第二种模型左闭右开因为当 left 等于 right 时区间已经为空。如果你采用的模型是左闭右闭循环条件就必须写成while (left right)因为当 left 等于 right 时区间里还有一个元素不能直接退出。上面那段错误代码的问题就很清晰了它写了right nums.size()这是左闭右开的初始化循环条件也用对了但在收缩 left 时却用了left mid。在左闭右开模型下left 是闭区间端点mid 已经被排除在搜索范围之外了所以正确做法是left mid 1。区间模型、循环条件、收缩方向三者必须来自同一个配套体系混搭必翻车。这就是边界的本质——不是某一行的错而是整套规则的内部不一致。1.3 区间模型决定一切左闭右闭与左闭右开我把两种主流区间模型放在一张表里方便你对照。后面每一节的推导都会围绕这张表展开。模型初始 right循环条件left 收缩right 收缩循环结束时 left/right 含义左闭右闭 [left, right]n - 1left rightleft mid 1right mid - 1left right区间为空左闭右开 [left, right)nleft rightleft mid 1right midleft right区间为空注意看左闭右闭和左闭右开连循环结束时 left 和 right 是否相等都不一样。理解这一点你就明白为什么网上各种模板看起来差不多但细节全部对不上号。你不需要两套都背但你必须清楚自己写的是哪一套并且让所有配套语句服从这一套。我强烈建议初学者先选定左闭右闭或左闭右开其中一种把它的推导过程过十遍以上再接触另一种。2. 左闭右闭 [left, right]最符合直觉的完整推导与标准代码2.1 初始区间和循环条件的自洽关系左闭右闭模型的想法很直接left 指向区间第一个元素right 指向区间最后一个元素两个端点都包含在搜索范围内。所以初始化是int left 0; int right nums.size() - 1;当数组为空时nums.size() - 1会变成 -1左闭右闭模型下这代表最大索引比最小索引还小区间为空这没问题只要循环条件能正确处理。循环条件必须写成while (left right)。为什么因为当 left right 时区间 [left, right] 里还有一个元素 nums[left] 没有被检查过它完全可能是目标值。如果写成left right这个唯一的元素就被漏掉了。这里又引出一个常见坑把初始 n-1 和循环配对目标值落在最后一个索引上时查不到。2.2 为什么相等分支必须用 mid1 和 mid-1而不是 mid在左闭右闭模型里一旦nums[mid] ! targetmid 就永远不可能是答案了所以收缩时要把 mid 从区间里剔除。当nums[mid] target时目标值只可能在 [mid1, right] 中所以 left mid 1当nums[mid] target时目标值只可能在 [left, mid-1] 中所以 right mid - 1这一步至关重要只有 mid 被排除区间长度才会严格减小循环才可能在有限步内结束。如果你写成left mid当区间长度为 2 时就会像第 1 节那样陷入死循环。完整的标准实现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; }用nums [1, 3, 5, 7, 9]手推一遍target 4的过程初始 left0, right4mid2nums[2]5 4right 1left0, right1mid0nums[0]1 4left 1left1, right1mid1nums[1]3 4left 2left2, right1此时 left right退出循环返回 -1每一步区间都在缩小最终正常结束。2.3 求中间值最容易忽略的整数溢出坑很多教材写int mid (left right) / 2这在面试和刷题中其实不推荐。left right可能溢出尤其在数组很大的时候。比如 left 接近INT_MAX - 1、right 也接近INT_MAX时两者相加直接溢出成负数mid 变成负数数组越界访问查错时会非常困惑因为你可能根本想不到是加法溢出了。更稳妥的写法是int mid left (right - left) / 2;这个公式的本质是把两个端点的平均值改写成左端点加上区间长度的一半避免了先相加再相除带来的溢出风险。如果追求位运算提速还可以写成left ((right - left) 1)注意移位运算符的优先级低于加法所以括号不能省。在工程里这点性能差异几乎可以忽略关键是别写错。我在实际项目里见过一次极其隐蔽的 bug一个大文件索引系统用二分查找偏移量文件超过 2GB 后left right直接溢出查后面的数据就莫名失败。排查了很久才定位到这一行。从那以后我所有二分代码一律写left (right - left) / 2没有任何例外。3. 左闭右开 [left, right)另一套思维另一种优雅3.1 while (left right) 的秘密左闭右开模型的思想是left 指向搜索区间的第一个可能元素right 指向区间右侧第一个不可能的元素。初始时整个数组是 [0, n)所以int left 0; int right nums.size();这个初始化有个天然的优点当数组为空时 right 0不需要像左闭右闭那样处理 -1。循环条件写while (left right)因为当 left right 时区间为空已经没有元素需要检查了。在左闭右开模型里绝不能用left right否则当 left 和 right 相等时nums[left] 可能越界访问——right 初始是 n收敛到 n 时 nums[n] 根本不合法。3.2 收缩方向里藏着的数学美感在左闭右开模型下收缩规则是当nums[mid] target时left mid 1mid 被排除新的左区间从 mid1 开始当nums[mid] target时right midmid 被排除新的右边界是 mid因为右侧区间是 [left, mid)这里最容易被问住的就是为什么大于 target 时 right 不改写成mid - 1因为在左闭右开模型里right 本身就不包含在区间内。区间是 [left, right)如果改成right mid - 1你不仅排除了 mid还会把 mid - 1 也排除掉可能误杀目标值。这个细节一旦想通整套模型就通了。标准实现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; }再看之前那个死循环例子nums[1,3,5,7,9], target4left1, right2 时 mid1nums[1]3 4执行 left mid 1 2区间变成 [2,2)为空循环退出。问题迎刃而解因为 left 永远不会原地踏步。3.3 为什么 C 的 lower_bound 选择左闭右开你会发现 C STL 的lower_bound、upper_bound以及binary_search都采用左闭右开模型。这绝不是偶然而是因为 STL 的迭代器设计本身就遵循begin 指向第一个元素end 指向最后一个元素的下一个位置的惯例。迭代器区间 [first, last) 统一了所有容器的边界语义也让返回插入位置变得更自然当查找不到目标时lower_bound返回的位置正好是第一个不小于 target 的元素的位置可以直接作为插入点而不需要额外判断。在纯算法题里左闭右开模型还有一个隐蔽的好处它天然支持查找第一个大于等于/第一个大于目标值这类变体。第 4 节我会展示它如何统一处理插入位置。如果你以后要写有序数组插入、区间合并、离散化去重这类逻辑左闭右开是更省心的选择。4. 从找目标到找边界三个高频变体的统一解法二分查找常见的变体远不止找 target 是否存在这么简单。面试和实际工程里更常遇到的是下面三个问题查找数组中第一个等于 target 的位置查找数组中最后一个等于 target 的位置查找 target 应该插入到哪个位置即第一个大于等于 target 的位置也就是 lower_bound这几个问题看似不同但底层逻辑完全一样区别只在等号的处理和返回值上。4.1 查找第一个等于 target 的值把等号交给右边界思路用左闭右开模型把区间边界不断向第一个满足条件的元素收拢。比较时如果nums[mid] target说明第一个等于 target 的元素在 mid 或 mid 左边于是收缩右边界right mid如果nums[mid] target说明 mid 左边全部小于 target收缩左边界left mid 1。int lowerBound(vectorint nums, int target) { int left 0, right nums.size(); while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid; } } return left; }循环结束后left 指向的是第一个不小于 target 的元素的位置。此时既可能找到了第一个 target也可能 target 根本不存在需要额外检查int firstEqual(vectorint nums, int target) { int pos lowerBound(nums, target); if (pos nums.size() nums[pos] target) return pos; return -1; }注意pos nums.size()这个判断不能省。target 比数组中所有元素都大时left 会一直增大到 n直接访问 nums[n] 就是越界。4.2 查找最后一个等于 target 的值必须处理 mid 向上取整查找最后一个等于 target 的元素等价于查找第一个大于 target 的元素位置减一。可以用 upper_bound第一个大于 target 的位置再减一也可以直接调整二分逻辑。这里容易踩一个大坑我单独拎出来演示。用左闭右闭模型直接写找最后一个等于 target时如果不小心选择向下取整的 mid就会死循环。// 错误示范会死循环 int lastEqual(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { // 注意这里假设至少有一个 target int mid left (right - left) / 2; // 向下取整 if (nums[mid] target) { left mid; // 可能原地踏步 } else { right mid - 1; } } return left; }问题场景left1, right2nums[1] target 成立mid 1left mid 1区间不收缩死循环。解决办法是让 mid 向上取整int mid left (right - left 1) / 2;这样当 left1, right2 时mid (121)/2 2区间必然收缩。更稳妥的工程写法是用 lower_bound upper_bound 组合把找第一个/最后一个统一成找位置区间int leftPos lowerBound(nums, target); int rightPos upperBound(nums, target) - 1; // 最后一个等于 target4.3 一套模板收服所有变体拿实例跑一遍用nums [1, 3, 5, 5, 5, 7, 9]验证上面几个函数targetlowerBound 返回值firstEquallastEqual含义5224目标等于 5 的区间是 [2, 4]65-1-1应插入下标 5原数 7 会被往后挤00-1-1应插入下标 0107-1-1应插入下标 7数组尾部看到这里你应该明白了lower_bound 并不是只能找 target它本身就是插入位置的通用解。在有序数组中插入元素、构建可重复数值的离散化映射、处理区间查询时很多时候你需要的不是找不找得到 target而是第一个大于等于 target 的位置在哪。把 lower_bound 想透上面所有变体就都有了解法。5. 实际排查实录死循环、越界、漏查的完整复盘我自己排过的二分 bug 里有三次特别典型。每次复盘后我都发现问题不是算法不会而是规则混用或者边界判断漏了分支。这里把完整排查链路写出来希望你能少走弯路。5.1 死循环案例mid 不收缩导致 left/right 原地打转现象nums [1, 2, 3], target 2的查找第一个等于 target 的代码提交后一直超时。排查步骤在循环体首尾打印left, right, mid发现某轮迭代 left1, right2mid1nums[1] target于是执行right mid 1下一轮 left1, right1区间为空循环应该结束——但如果循环条件写成了while (left right)就会继续进入循环体下一轮 mid1再次执行right mid 1然后发现 left、right 永远都是 1死循环根因左闭右开模型下循环条件必须是left right。当区间收缩到空时left 和 right 相等恰恰是终止条件你却用了把空区间又放回了循环里而 mid 又没法推进区间于是卡死。排查这类问题的通用方法先在循环末尾打印区间状态如果出现left、right 连续多轮不变化说明收缩规则存在死角。此时检查你写的是不是成了left mid或right mid与区间模型的搭配。5.2 越界案例返回 left 前没检查是否等于 nums.size()现象实现 lower_bound 后对nums [1], target 3调 firstEqual程序崩溃报 heap-buffer-overflow。排查步骤手推left0, right1mid0nums[0]1 3left 1循环结束返回 left1firstEqual 里直接访问 nums[pos]pos 1越界根因left 在所有元素都小于 target时收敛到 n也就是数组尾部之后。这是合法插入位置但不是合法访问位置。凡是 lower_bound 之后要访问数组的必须加pos n或pos 0的边界检查。这个坑在 C 里最容易踩因为 vector 的operator[]不做越界检查越界后行为是未定义的测试时可能恰好读到旧内存线上才随机崩溃。Java 和 Python 会直接抛异常反而容易定位。5.3 等号混乱案例把 写成 造成漏查现象标准左闭右闭二分nums [1, 2, 3], target 1返回 -1但 target 明明在数组里。排查步骤打印每轮 left、right、mid第一轮 left0, right2mid1nums[1]2 1right mid - 1 0循环条件如果写成while (left right)此时 left0, right0循环退出返回 -1根因左闭右闭模型下当 left right 时区间还有一个元素 nums[0] 没查。让这个唯一元素被跳过。把循环条件改成left right即可。这个案例说明排查二分问题不能只看 if 分支里的比较符还要连坐检查循环条件。一套规则里的所有符号都是配套的单独怀疑任何一处都可能找不到根因。这类问题我用过一个很笨但有效的办法把 left、right、mid 的每一轮值手写在纸上模拟三到五轮。一旦某轮出现区间不收缩或漏查某个索引基本就能定位到是哪个符号错了。比起纯靠眼睛盯代码手推一遍速度快得多。6. 写二分前我必做的三件事从源头消灭边界问题6.1 先用 1 个元素和 2 个元素的用例做契约试验这个习惯救过我很多次。写完二分代码先用长度 1 和长度 2 的数组做四组测试目标在数组前、目标在数组中间针对长度 2、目标在数组尾部、目标不存在于数组中。长度 2 的数组特别容易暴露死循环因为区间收缩中的原地踏步往往发生在 left 和 right 相邻时。举个例子nums [1, 2]测 target 2。左闭右闭模型下left0, right1mid0nums[0]1 2left1leftright区间 [1,1] 还有一个元素 nums[1]2此时循环条件若是就继续查命中返回若是就退出漏查。这样一个 2 元素用例直接检验出循环条件和收缩规则是否配套。我通常把这四组用例写在测试函数的注释里每次改完二分都先跑一遍。6.2 把不变量写进注释代码是给下一个维护者看的二分查找的代码极其紧凑一两行就能写完但你离开三天后回来看很可能想不起来当时为什么要写right mid而不是right mid - 1。所以我在实际工程里有一条硬性要求二分函数里必须有一行注释写明循环不变量。比如// 每次迭代开始前[left, right) 内是 target 可能存在的区间 // 循环结束且未返回时left righttarget 不存在别小看这一行注释。它约束的不只是后来者更是写代码那一刻的你自己。只要注释写清楚了left 和 right 各自代表什么你再写循环条件时就不会随手写错。有一次我 review 同事代码他把左闭右开模型的标准写法抄过来却把right nums.size()写成了nums.size() - 1我通过注释一眼就发现区间语义对不上了——他要找的最后一个元素被开区间端点排除在外。这种问题靠跑用例也能发现但靠注释能在提交前就拦下来。6.3 背模板不如推模板为什么我建议你掌握推演过程网上有很多二分模板有的总结成三个分支、两个端点、一个循环条件有的干脆叫你背下来。我理解这种做法的初衷但它有个致命问题模板给的是结论不是推理。一旦题目变化比如从普通数组变成二维矩阵、从查精确值变成查旋转数组最小值模板的某个细节就可能不适用而你不知道该改哪里。我建议你把二分放在不变量的框架下去理解。无论是左闭右闭还是左闭右开只要做三件事明确区间定义端点是否包含推导循环条件区间何时为空验证收缩规则mid 被排除后新区间是否完整覆盖所有可能这三步推完你的代码自然就写出来了不需要背。有一次我在项目里要手写一个在日志时间戳数组里找最后一个早于给定时间的位置就是按照这三步推的先想清楚右端点含义再确定向上取整几分钟就写对了。如果当时只会背模板遇到这种不等二分大概率要卡壳。再说句题外话很多人在工程里坚持用标准库的lower_bound这是对的。手写二分只在算法题、教育场景或标准库无法覆盖的定制需求里才有必要。但即便如此把边界推演能力练扎实绝对不亏。它训练的是你对区间不变式的敏感度这种能力在写归并排序、线段树、平衡树时一样用得上。写二分这么多年我最深的体会是它考的不是会不会用 if else而是敢不敢把隐藏的假设亮出来。边界处理之所以难是因为它逼你把为什么 left 要加一、right 为什么不减一这类平常根本不会想的问题想清楚。一旦你想清楚了二分查找就不再是背了又忘、忘了又背的烦恼而是一个闭上眼都能推出来的基本功。