1. 二分查找真正难的地方从来不是找中间值1.1 同一道题十个人能写出十种边界我做过一个小统计在同一个学习小组里让 12 个人写在有序数组里找第一个大于等于 target 的位置最后收上来 12 份代码边界条件几乎没有两份是完全一样的。有人写left 0, right n - 1配while (left right)有人写left 0, right n配while (left right)有人在返回的时候纠结到底该返回left还是left - 1更常见的是代码写完跑样例过了提交上去卡在第 7 个测试点对着屏幕改1、-1改到怀疑人生。问题出在哪出在绝大多数人学二分查找的时候学的是一段代码长什么样而不是这段代码在维护什么。大家记住的是mid 1和mid - 1这两个动作却没人告诉你这两个动作背后的含义是——我刚才验证过mid 这个位置肯定不是答案所以把它踢出搜索范围。一旦你脑子里没有搜索范围这个概念1和-1就变成了纯粹的玄学符号这里该加还是该减全凭感觉凭感觉写代码早晚翻车。关键词里提到的mid1、mid-1本质上不是二分的必需品而是某一种区间表示法的副产品。换一种区间表示法它们就彻底消失了。1.2 用猜数字把区间不变量讲明白先做个游戏。我心里想了一个 1 到 100 之间的整数你来猜我只会回答大了、小了或者对了。你大概率会这样猜先猜 50。我说小了你就知道答案在 51 到 100 之间再猜 75我说大了范围缩到 51 到 74如此往复最多 7 次一定能猜中。这个游戏里藏着一个关键事实你每一步都在维护一个答案一定在里面的区间。这个性质术语叫循环不变量。二分查找卡边界百分之九十的原因就是——代码跑到第三步的时候区间已经不满足这个性质了但你还不知道。举个真实的例子。很多人的写法是这样的int left 0, right n - 1; while (left right) { int mid (left right) / 2; if (nums[mid] target) left mid 1; else right mid - 1; } return left;这份代码在什么情况下是对的答案是当数组里确实存在 target且你只想找任意一个等于 target 的位置时它是能跑通的后面还得再单独处理找不到的情况。但如果你想找的是第一个大于等于 target 的位置right mid - 1这一句就闯祸了——因为当你发现nums[mid] target时mid 本身极有可能就是答案你把它减掉答案就被你亲手丢到区间外了。你看这就是mid - 1的危险之处它不是不能减而是你得先确认这个位置可以减。而确认这件事需要你在脑子里同时维护区间定义和比较规则两套逻辑人一紧张就容易顾此失彼。1.3 我为什么最后还是放弃了left right的写法坦白说left right加全闭区间[left, right]的写法并没有错写熟了也很快。但它在教学和实际工程里有三个绕不开的麻烦。第一个麻烦是返回值的歧义。循环结束时left一定等于right 1这时候left到底是答案位置还是答案不存在时该插入的位置需要看具体分支很容易搞混。做业务的时候一个下标差一位可能就是用户排在队伍第 5 位和第 6 位的区别。第二个麻烦是变体太多。找存在、找左边界、找右边界、找插入位置、找最后一个小于等于的——每种都要重新推一遍边界。我见过太多人把这些做成一个我记得好像是这样的列表而不是从同一个原理推出来的。第三个麻烦是和标准库语义对不上。C 的std::lower_bound、Python 的bisect_left返回的都是第一个不小于目标值的位置它们的内部实现用的就是两个指针逐渐靠近、最后相邻的思路而不是left right那一套。你如果想把手写二分的习惯和标准库的语义统一起来用相邻收敛的写法会顺得多。所以我后来固定下来一套模板让 left 和 right 始终代表两个相邻的哨兵循环只做一件事——把它们之间的空隙不断缩小直到相邻为止。这套模板里全程只有left mid和right mid两种赋值没有1没有-1也没有到底该不该加一的纠结。注意不是说带1/-1的写法不能用而是说对绝大多数人来说选一套不需要做减法判断的模板能显著降低出错概率。这是工程上的取舍不是信仰之争。2. 核心思路让两个哨兵慢慢靠近答案自己浮出来2.1 三条铁律不变量、严格收缩、终止条件整篇内容其实就围绕三条规则展开把这三条记住剩下的都是套用。第一条不变量整个循环过程中始终保证答案一定落在(left, right]这个范围内也就是左开右闭。换句话说left是一个已知不满足条件的位置right是一个可能是答案的位置。第二条严格收缩每一轮循环区间长度必须变小。这一点由 mid 的位置保证——因为 mid 永远严格落在left和right之间无论走哪个分支区间都会缩小。这一点后面会给出证明。第三条终止条件循环继续的条件是right - left 1也就是只要两个哨兵还不相邻就继续找。当right - left 1时停下来此时right就是答案。把这三条翻译成一段大白话我左边插一个肯定不行的牌子右边插一个答案就在这附近的牌子然后我每次往中间探一步根据探到的结果决定把哪块牌子往中间挪。挪到最后两块牌子挨在一起右边的牌子站的位置就是答案。2.2 区间边界怎么设为什么 left 要从 -1 开始right 要到 n这是初学者最不适应的地方left初始值写成 -1right初始值写成n数组长度看起来像是越界了。其实一点问题都没有因为这两个值是哨兵不是数组下标。left -1表达的意思是下标 -1 这个位置以及它左边所有位置都不满足条件——这是一个永远成立的空断言因为根本没有下标 -1。同理right n表示如果前面都没有答案那么答案就是 n也就是不存在的编码。拿找第一个大于等于 target 的位置举例条件设定为nums[i] targetleft -1表示下标 -1 不满足nums[i] target天然成立right n表示下标 n 满足条件这是我们人为约定的兜底用来表示找不到循环结束时返回right如果right n就说明数组里所有元素都小于 target。这样做的好处是边界统一。你不需要为数组为空、目标比所有元素都小、目标比所有元素都大这三种情况单独写 if 分支——空数组时left -1, right 0循环一次都不进直接返回 0语义正好是第一个大于等于的位置是 0合理。我见过最典型的一个翻车场景是数组里所有元素都比 target 小需要返回应该插入的位置 数组长度。用全闭区间写法的人经常返回left得到n - 1或者直接数组越界用相邻收敛写法的人一行不用改返回n天然正确。2.3 这套模板为什么一定不会死循环死循环是二分查找最让人抓狂的问题程序不报错就是不结束本地跑小数据还看不出来一提交就超时。相邻收敛的模板可以从数学上证明不会死循环。设当前区间长度为d right - left。循环能进来说明d 2。mid 的取法是mid left (right - left) / 2 // 整数除法向下取整因为d 2所以d / 2 1于是mid left 1 leftmid 严格大于 left。同时又因为d / 2 d - 1当d 2时成立d 2时两边都是 1所以mid left d - 1 right - 1 rightmid 严格小于 right。两边一夹得到left mid right。那么无论走哪个分支走left mid新区间长度是right - mid因为mid left所以新长度一定小于原来的d走right mid新区间长度是mid - left因为mid right新长度也一定小于原来的d。两种情况区间长度都严格递减而长度是正整数所以必然在有限步内降到 1循环退出。对比一下就会发现问题所在很多死循环的写法是因为mid可能等于left。比如mid (left right 1) / 2向上取整配上left mid当只剩两个元素时 mid 就等于 right如果走left mid分支区间长度没变就会原地打转。相邻收敛模板靠向下取整 left mid right这个组合把这个坑从根源上堵死了。提示判断一个二分会不会死循环最快的办法不是跑代码而是问自己一句——这一轮循环里区间长度有可能不变吗只要有可能不变就得警惕。3. 三套代码把模板的变体一次讲透3.1 C 版本手写 lower_bound 与 upper_bound先把最核心的一个版本写出来它对应 C 标准库里的std::lower_bound// 返回第一个满足 nums[i] target 的下标 // 若所有元素都小于 target返回 nums.size() int lowerBound(const std::vectorint nums, int target) { int left -1; // 哨兵一定不满足 int right static_castint(nums.size()); // 哨兵候选答案 while (right - left 1) { // 只要不相邻就继续 int mid left ((right - left) 1); if (nums[mid] target) { left mid; // mid 确定不满足把左哨兵挪过来 } else { right mid; // mid 可能是答案右哨兵挪过来 } } return right; // 相邻时 right 就是答案 }注意这里mid的计算用了left ((right - left) 1)而不是(left right) / 2。原因很实际当left和right都是接近INT_MAX的大数时left right会溢出成负数mid直接变成非法下标程序崩溃或者死循环。改成先减后加差值最大也就是数组长度绝对安全。这个问题在笔试里真的会考我至少在三家公司的笔试题里见过下面这段二分为什么会崩的判断题。再看upper_bound也就是第一个严格大于 target 的位置// 返回第一个满足 nums[i] target 的下标 int upperBound(const std::vectorint nums, int target) { int left -1; int right static_castint(nums.size()); while (right - left 1) { int mid left ((right - left) 1); if (nums[mid] target) { left mid; // 只有 才往左挪 } else { right mid; } } return right; }你会发现两个函数只差一个等号。lower_bound里是nums[mid] targetupper_bound里是nums[mid] target。这不是巧合而是这套模板最舒服的地方改条件就行不用动结构。有了这两个函数判断target 是否存在就变成两行int pos lowerBound(nums, target); bool exists (pos (int)nums.size() nums[pos] target);最后一个小于等于 target 的位置也可以直接套// 返回最后一个满足 nums[i] target 的下标不存在返回 -1 int lastLessEqual(const std::vectorint nums, int target) { int left -1; int right static_castint(nums.size()); while (right - left 1) { int mid left ((right - left) 1); if (nums[mid] target) { right mid; // 大于 target排除 } else { left mid; // 小于等于有可能是答案 } } return left; // 注意这里返回的是 left }注意这个版本返回的是left而不是right。为什么因为这里的语义是找最后一个满足条件的答案应该在左哨兵这一侧。判断依据很简单循环结束时 left 和 right 相邻谁的初始语义是候选答案就返回谁。前面两个版本里 right 是候选所以返回 right这个版本里我们把可能是答案的一方放在左边所以返回 left。3.2 Python 和 Java 移植时的取整陷阱同样是这套模板换语言写的时候有两个坑。Python 版本def lower_bound(nums, target): left, right -1, len(nums) while right - left 1: mid (left right) 1 if nums[mid] target: left mid else: right mid return rightPython 里对负数会向下取整但由于 mid 恒为正数范围left 最小是 -1(-1 0) 1 -1这种情况只在区间长度为 1 时出现而循环已经退出了所以这里不会出现负数右移的歧义。稳妥起见你也可以直接写mid (left right) // 2语义更直白。Python 最大的优势是整数不溢出所以(left right) // 2随便写。这也导致一个常见现象从 Python 转到 C 的人习惯性写(left right) / 2在大数据量、大下标场景下就会翻车。Java 版本static int lowerBound(int[] nums, int target) { int left -1; int right nums.length; while (right - left 1) { int mid left ((right - left) 1); if (nums[mid] target) { left mid; } else { right mid; } } return right; }Java 的取整是向零取整这一点在处理负数时和 Python 不一样。好在我们的 mid 永远是非负的所以 1和/ 2结果一致。不过我还是习惯写 1因为它对int明确无歧义而且能顺便提醒自己这是位运算不是整除。另外顺便提醒一个 Java 的坑Arrays.binarySearch找不到元素时返回的是-(插入点) - 1而不是-1。这个设计当年坑了不少人用它做第一个大于等于的时候必须手动转换int pos Arrays.binarySearch(nums, target); if (pos 0) pos -pos - 1; // 转换成插入位置语义如果你用上面自己写的模板就完全不需要记这种特殊约定。3.3 二分答案版本把 check 当答案预测器真正让我觉得相邻收敛模板值得推广的是它在二分答案类问题上的表现。这类题的形态是求一个最小的/最大的整数 x使得某个性质check(x)成立并且这个性质具有单调性——x 一旦成立更大的 x 也成立或者反过来。模板长这样// 求最小的满足 ok(x) true 的 x // 前置条件ok(lo - 1) falseok(hi) true int binaryAnswer(int lo, int hi, const std::functionbool(int) ok) { int left lo - 1; // 哨兵一定不满足 int right hi; // 哨兵一定满足 while (right - left 1) { int mid left ((right - left) 1); if (ok(mid)) { right mid; // mid 满足答案可能是它或更小 } else { left mid; // mid 不满足往右找 } } return right; }看清楚了吗——结构一字未改。变的只有两处一是把nums[mid] target换成ok(mid)二是把初始的left/right换成lo - 1 / hi。这就是我想强调的所谓二分查找和二分答案本质上是同一套骨架只是一个在比较数组元素一个在比较谓词函数。我在实际写题时会做一件小事先在草稿纸上写下答案的单调方向这句话比如时间越长越可能完成任务所以 check 随 x 单调递增。写下这句话之后if (ok(mid)) right mid; else left mid;到底谁往左谁往右就是自动推导出来的一点不用猜。如果要求的是最大的满足 ok(x) 的 x套路一样只是把主谓词取反或者干脆把左右哨兵的语义互换// 求最大的满足 ok(x) true 的 x // 前置条件ok(lo) trueok(hi 1) false int binaryAnswerMax(int lo, int hi, const std::functionbool(int) ok) { int left lo; // 哨兵一定满足 int right hi 1; // 哨兵一定不满足 while (right - left 1) { int mid left ((right - left) 1); if (ok(mid)) { left mid; } else { right mid; } } return left; }我个人的经验是不要同时维护两套最大/最小模板只留一套另一套靠取反实现。脑子里的模板越少出错概率越低。比如要求最大的满足条件的 x你就去二分最小的不满足条件的 x然后减一效果完全一样。4. 实战场景这套模板能覆盖的六类高频题型4.1 查找类存在性、插入位置、左右边界这是最基础的用法也是面试里出现频率最高的一类。给定一个排好序的数组常见需求有五种需求描述判定条件写法返回第一个 target的位置nums[mid] target时左移right第一个 target的位置nums[mid] target时左移right最后一个 target的位置nums[mid] target时右移left最后一个 target的位置nums[mid] target时右移left元素是否存在用第一条再校验布尔值你会发现这张表里没有一行涉及mid 1或mid - 1。这就是模板的价值把边界调整这件事从代码里彻底删掉了。顺便说一个实际工作中的用法。做过接口开发的人应该都遇到过区间统计的需求比如统计某个时间区间内的订单量。如果订单时间戳数组是有序的很多场景下确实按时间写入那么区间[t1, t2]内的订单数就是count upperBound(t2) - lowerBound(t1)两行代码O(log n) 复杂度不用遍历整个数组。这种写法我在日志分析、监控数据聚合的场景里用过很多次比 SQL 的BETWEEN配合索引还要直观——因为你知道它为什么是 O(log n)。4.2 最值类旋转数组、峰值、第 K 小第二类题的特点是数组不再全局有序但局部满足某种单调性。最经典的是旋转有序数组找最小值。假设数组是把一个升序数组从某处切断后拼接而成比如[4,5,6,7,0,1,2]。要找最小值仍然可以用相邻收敛模板只是判定条件要换成mid 落在哪一段int findMinInRotated(const std::vectorint nums) { int left -1; int right static_castint(nums.size()) - 1; // 最小值一定在 [0, n-1] 内收敛到 left 侧 while (right - left 1) { int mid left ((right - left) 1); if (nums[mid] nums[right]) { left mid; // 说明 mid 在左半段最小值在 mid 右边 } else { right mid; // mid 在右半段最小值可能就是它或更左 } } return nums[right]; }这里的初始边界和前面的版本略有不同right取n - 1而不是n因为数组非空时最小值一定存在不需要找不到这个语义。这提醒我们一件事——模板的结构是固定的但初始哨兵要根据答案是否存在来定。答案一定存在就不需要n这个兜底位。另一类高频题是找峰值元素相邻元素不相等找出任意一个比左右都大的位置。判定条件写成nums[mid] nums[mid 1]则在上升段峰值在右侧同样可以套模板。写的时候注意mid 1的越界保护——这里的1是数组下标访问不是区间调整两回事。第 K 小这一类问题如果数据范围允许往往可以转化成二分答案 计数也就是下一节的内容。4.3 二分答案类最大值最小化、最小值最大化这是我个人认为二分思想最迷人的应用场景因为它把求解问题变成了判断问题。典型题目形态有 n 个物品要分到 m 个容器里求所有容器中最大的那一份最小是多少。这类问题直接求很难但如果换一个问法——给定一个上限 X能不能在 m 个容器内装下——就变成了一个简单的贪心判断能在 O(n) 时间内给出答案。而这个判断函数对 X 是单调的X 越大越容易装下。于是二分 X 即可。模板套用过程bool canPack(int limit, const std::vectorint items, int buckets) { int used 1, cur 0; for (int w : items) { if (w limit) return false; // 单个就超了直接不行 if (cur w limit) { used; cur w; } else { cur w; } } return used buckets; } int minMaxWeight(const std::vectorint items, int buckets) { int lo *std::max_element(items.begin(), items.end()); int hi 0; for (int w : items) hi w; return binaryAnswer(lo, hi, [](int x) { return canPack(x, items, buckets); }); }注意这里的lo和hi不是随便取的lo取单个物品的最大值因为任何一个容器的上限不可能小于最大的那个物品hi取所有物品总和一个容器全装下肯定可行。二分的下界和上界取得越紧循环次数越少——这不是性能上的吹毛求疵而是做题时避免答案不在区间内这个致命错误的关键。我在这一块踩过的最大的坑是lo取成了 0结果某些测试点里canPack(0)的行为没有定义比如除零、或者下标越界直接运行时错误。二分的可行域一定要包含答案且哨兵值必须落在函数定义域内。5. 常见问题与排查技巧实录5.1 症状对照表死循环、答案差一、越界写了这么多年代码二分出错的表现其实就那么几种。我整理了一张对照表出问题的时候直接查表比漫无目的地加打印快得多。症状大概率原因修复方向程序一直不结束mid 取了向上取整或分支赋值没有严格收缩改回向下取整检查left mid right答案总是差 1哨兵初始值设错或返回了错误的一侧检查返回 left 还是 right 与语义是否匹配数组越界mid 溢出成负数或初始 right 写成 n 却当索引用用left (right - left) / 2明确哨兵语义样例过、提交错只测了能找到的情况没测空数组/全大于/全小于补三类边界用例结果在部分区间正确判定条件写反方向用一句答案随 x 单调递增/递减重新推导这张表里最值得展开的是答案总差 1。它的根源几乎永远是语义不匹配你脑子里想的是第一个满足条件的位置代码却返回了最后一个不满足条件的位置。这两个值在数组里恰好相邻所以只在某些用例上表现正确特别有迷惑性。解法很土但很有效在纸上画一行 6 个元素把 left 和 right 画成两个箭头手动走一遍循环。看着箭头一步步靠拢比盯着代码想强十倍。5.2 调试三板斧打印区间、小数据对拍、断点记 mid第一板斧打印区间。在循环体第一行加一句输出把每一轮的left、right、mid、nums[mid]全打出来。只要看一眼区间是不是每轮都在变小死循环的问题立刻就定位了。round 1: left-1 right6 mid2 nums[2]5 round 2: left-1 right2 mid0 nums[0]1 round 3: left0 right2 mid1 nums[1]3 round 4: left1 right2 - stop, answer2第二板斧小数据对拍。写一个 O(n) 的暴力版本然后随机生成几百组小规模数组长度 1 到 10值域 0 到 5故意制造大量重复元素逐组对比两个版本的结果。二分的错误往往只在特定长度上暴露手动构造用例很难覆盖随机对拍几分钟就能把它们全揪出来。重复元素这一点特别重要。很多人的二分在元素互不相同时完全正确一遇到重复就跑偏因为判定条件里的和选错了。生成随机数据的时候值域一定要设得足够小逼出大量重复。第三板斧在断言里记 mid。如果是在写竞赛代码或者业务代码可以加一句assert(mid left mid right mid 越界二分不变量被破坏);平时它是零成本的Release 构建会去掉一旦不变量被破坏程序立刻在出问题的位置停下来而不是等到几分钟后死循环超时。这一招我在写复杂二分答案的时候经常用。5.3 我踩过的坑与经验总结最后说几个只有真正写过才印象深刻的细节。第一个坑是下界为负的二分。有一类题要求答案可能是负数比如求最小的 x 使得某个函数值非负x 的取值范围是[-1e9, 1e9]。这时候如果 mid 的取整方向没考虑清楚很容易在负数区间上出现区间不收缩。前面证明了left mid right时向下取整是安全的这个结论对负数同样成立——因为它是基于差值right - left推导的和绝对值的正负无关。但如果你改用了向上取整那就得重新推一遍。我的建议是永远只用向下取整永远只维护left mid right不要在大脑里同时装两套取整逻辑。第二个坑是浮点数二分不要用这套整数模板。浮点二分一般写成固定循环 100 次或者判断right - left eps这时候不需要纠结取整因为浮点数不会因为取整而卡住。我见过有人把整数模板硬套到浮点问题上用while (right - left 1)结果循环一次都不进直接返回初始的右哨兵。两套东西别混。第三个坑是**边界收敛和提前返回不要同时用**。有些人喜欢在循环里写if (nums[mid] target) return mid;同时又用相邻收敛结构。这在找任意一个的题目上没问题但如果你要找的是第一个等于 target 的位置提前返回会破坏正确性因为它可能返回中间那个而不是最左边那个。要么全程不提前返回靠收敛位置说话要么就别用这套模板。我个人的做法是全程不提前返回虽然平均多跑一两次循环但逻辑干净不容易出岔子。第四个是纯粹的经验把模板抄在自己的代码片段库里别每次重推。我见过太多人在面试现场临时推边界推到一半慌了最后写成四不像。模板的价值就在于它可以被机械地、不假思索地复用——结构不动只改那一行判定条件改完就能跑。真正需要动脑子的地方是这个问题的答案具有单调性吗以及下界和上界该取多少这两件事想清楚了代码几乎是自动生成的。我现在处理任何有序数据的边界查询需求第一反应就是先写出left -1; right n;这两行然后问自己一句我要找的是哪一个边界。剩下的部分就是把判定条件填进去而已。这套流程用久了会有一种踏实感——你知道每一行代码为什么在那里也知道它为什么不会出错。