二分查找是那种“你觉得你早就会了一写就错”的算法。这些年我帮不少朋友同学review过代码也自己在各种竞赛题、面试题和PTA作业里反复写过它最深的一个感受是背模板的人多真正理解区间含义的人少。你问他边界为什么这样写他说“因为模板就是这样”你让他换个题目找“最后一个小于target的位置”他直接卡住。这篇文章我想把这几年用下来最顺的一套理解方式完整整理出来——从二分查找的本质、三种经典写法的边界差异、死循环和溢出这些经典坑到二分答案、PTA函数题和实际调试方法一次讲透。适合正在学数据结构的新手也适合对边界处理一直心里没底的老手。1. 二分查找的本质不是在“猜数字”而是在“切分单调区域”1.1 你背下来的模板其实只处理了一种最特殊的情况学校里教二分查找起点永远是“在一个有序数组里找一个数”。这当然是对的但恰恰因为太特殊了把很多人的思路带窄了——他们以为二分查找的全部就是“排序数组相等判断”。我第一次真正觉得理解了这个算法是在想明白一句话之后二分查找做的事是不断切分一个满足单调性的区域直到明确答案在哪一边。数组里找一个数只是这个问题的一个退化版本。举个例子。你有一串数字1 3 5 5 5 7 9要找5出现的位置。常规做法是mid位置小于5去右边大于5去左边等于5直接返回。看起来很正常但“直接返回”这个动作恰恰暴露了模板的死穴——如果数组里有多个5你返回的这个5是不是最左边那个是不是最右边那个你根本不知道你只是“碰巧找到了一个”。而如果你换一种思维方式把整个数组看成一个由“是否满足某个条件”构成的序列位置 1 2 3 4 5 6 7 数值 1 3 5 5 5 7 9 条件 5F F T T T T T这个数列的 T/F 序列是F F T T T T T它有一个清晰的分界点从位置3开始变成 T。二分查找做的最核心的事就是找到这个分界点。至于找一个等于5的位置不过是找到这个分界点之后顺便解决了。1.2 把“数组”替换成“判定函数”视野立刻就打开了当你的思维从“在一个数组里找数”切换到“在一个单调的 0/1 序列上找分界点”之后二分查找的适用范围就大得惊人了。很多问题根本没有“数组”给你。典型的如竞赛和面试里常出现的“二分答案”让你求一个“最大值最小化”或“最小值最大化”的问题正向求解很难下手但你可以反过来——假设答案是一个数X然后写一个判定函数check(X)回答“这个 X 行不行”。如果X 可行那么所有比X 大的值也可行或者所有比X 小的值也可行取决于问题这就构成了一种单调性二分就成立了。经典的“切木棍”问题就是这样的给你若干根木棍要切出总数至少m段每段长度相同问你每段最长能切多长。正向直接求很难但如果你给定一个长度len检查“能不能切出不少于 m 段”——这个判定函数每个人都能写出来就是每根木棍对len整除然后求和。len越大能切出来的段数越少所以可以在长度范围上二分找到“段数不少于 m”的最大那个len。这就是把“求最值”变成“给个值验证行不行”的典型操作也是二分查找在生产环境中真正的价值所在。所以理解二分的本质只有一个关键点你的搜索空间必须具有单调性或者说存在一条把“可行”和“不可行”分开的边界线。有了这条边界线不管它是数组里的下标还是答案的取值范围二分都能用。2. 三种手写模板区间定义决定你每一行代码的写法网上流传最广的二分模板至少有三个版本区别只在区间开闭。很多新手不理解为什么有这么多写法以为是纯粹的风格问题。其实不是——不同区间定义下循环条件、收缩方向和最终返回位置都是被逻辑锁定的混用才会出 bug。2.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 size - 1因为闭区间必须包含size - 1。循环条件是left right因为当left right时区间里还有一个元素没判断不能退出。left mid 1和right mid - 1是因为mid已经被判断过了不可能是答案必须排除掉。这个模板简单直接但它有个明显的局限它假设你要找的“那个数”和左右的相等关系能直接告诉你答案。一旦问题是“找边界”“找第一个大于等于某个数的位置”它就显得别扭。2.2 左闭右开模板[left, right)最推荐这是我在实际刷题和写工程代码时用得最多的版本也是 C 标准库和很多教材采用的风格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; // 第一个 target 的下标 }这个模板的理解成本稍高但换来的是巨大的一致性收益初始right size表示区间[0, size)size本身不合法它只是“边界之外的哨兵”。循环条件是left right因为当两者相等时区间为空答案已经找到了。收缩时只有两条分支left mid 1或right mid。注意right mid而不是mid - 1因为区间是左闭右开mid不能被排除出右侧区间。循环退出时left right这个位置就是答案。这套模板的真正价值在于它天然支持“查找边界”不需要单独处理“相等”的情况。找第一个大于等于target的位置就是上面的代码找第一个大于target的位置只要把条件改成if (nums[mid] target)找最后一个小于target的位置结果是lowerBound(target) - 1。一套模板衍生出所有变体一旦熟练就不需要再背任何其他模板。2.3 开区间模板(left, right)还有一个经常被算法竞赛选手使用的版本我把区间写成(left, right)循环条件是left 1 rightint 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) left mid; else right mid; } return right; // 第一个 target 的下标 }这个版本理解的关键是left和right初始就被放在合法区间之外循环里left永远表示“已知不满足条件的最右侧位置”right永远表示“已知满足条件的最左侧位置”循环退出时它们相邻答案就是right。我个人觉得它很优雅但对初学者不太友好——因为left初始是-1很多人会把它当成越界错误。2.4 三种模板怎么选我给你的建议很简单如果是 PTA 作业或面试手写“找一个数”用闭区间模板最好懂别人也好 review。如果是刷题或写真实业务代码主推左闭右开模板它会逼你把所有变体都统一成一套写法减少记忆负担。开区间模板可以欣赏但除非你特别熟练否则别把它当作默认选择。下面这张表把这些区别收拢在一起方便对照模板初始区间循环条件收缩方式适用场景闭区间[0, n-1]left rightleft mid 1 / right mid - 1找单个确定值左闭右开[0, n)left rightleft mid 1 / right mid找边界、通用变体开区间(-1, n)left 1 rightleft mid / right mid竞赛写法边界语义清晰3. 边界与死循环最容易翻车的三件事二分查找的代码总共就五六行但错误率在所有基础算法里名列前茅。原因在于它的正确性依赖微妙的区间不变量肉眼几乎看不出问题只有跑到特定输入才爆炸。下面这三类问题是我见过最多的也是我自己反复踩过的。3.1 死循环的根源永远是“区间没有收缩”死循环的本质很简单某次迭代后新的区间和之前的区间完全相同于是while无限转圈。什么情况下会这样答案是left mid或right mid时mid恰好等于原来的left或right。最典型的翻车案例是有人写闭区间模板时偷懒这样收缩// 错误写法示意 while (left right) { int mid left (right - left) / 2; if (nums[mid] target) left mid; // 假设 left5, right6, mid5, 赋值后 left 还是 5 else right mid - 1; }当只剩两个元素left5, right6时mid left (right-left)/2 5如果走了left mid分支left还是 5新区间还是[5,6]死循环。面对这种情况我的自查方法是每写一次收缩就问自己“这个区间比上一轮严格变小了吗”如果left mid必须同时保证mid ! left如果right mid必须同时保证mid ! right。在左闭右开模板里mid恒大于left且恒小于right因为left right时left mid right所以left mid和right mid都是安全的这也是我推荐它的原因之一。3.2 整数溢出(left right) / 2的经典翻车现场大部分教材、课堂PPT和PTA参考题解里写的是mid (left right) / 2。这在数值很小的样例上没有任何问题一旦left和right都是 10 亿级别的数left right会直接越界变成负数mid变成一个荒唐的值程序要么死循环要么返回错误结果。很多 LeetCode 用户第一次被mid (low high) / 2坑到就是在超大数组的二分题目上。正确的写法是mid left (right - left) / 2。它为什么安全因为right - left最大不会超过数组长度不会溢出left (一个非负数)结果也始终在[left, right)内。这行代码应该成为肌肉记忆——不管题目范围再小都不要用(left right) / 2。也许有人会说“PTA judge 的数据范围那么小写(leftright)/2也没事”。但习惯是养成的面试官考察的就是你有没有把“潜在溢出”刻进直觉里。凡是可能规模大的场景写left (right - left) / 2永远是正确且不亏的。3.3 面对有重复元素时“等于”这个分支怎么处理很多人写二分找“等于 target 的位置”用闭区间模板时三分支都想得很清楚if (nums[mid] target) return mid; else if (nums[mid] target) left mid 1; else right mid - 1;这段代码在“只有一个目标值”时是对的但遇到重复元素时它返回的是“碰巧遇到的那一个”不是最左也不是最右位置不确定。如果你只是想知道“有没有”没问题但如果题目要求“第一个出现的位置”或“区间 [L, R] 内 target 出现了几次”这个模板就完全不够用了。处理办法就是把“等于”分支合并到严格不等号里——这也是我在第 2.2 节推荐的那个模板的精髓。你要找“第一个等于 target 的位置”可以写成int firstEqual(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; // 等于 target 也往左收 } if (left nums.size() nums[left] target) return left; return -1; }核心思路是“等于”不是返回的理由而是继续收窄边界的理由。想找最左侧就往左收想找最右侧就往右收。等你哪天真正接受了这套思路二分里的“相等分支”就不再是你的舒适区陷阱而是一个可操控的旋钮。4. 从“找一个数”到“找边界”二分真正的生产力如果你只会“找一个数”二分的价值只发挥了不到一半。实际应用里你经常需要知道的是第一个大于等于 X 的位置、最后一个小于 X 的位置、某个值出现了多少次、数组中有多少个元素落在某个区间里。这些都可以用两个基础操作拼出来。4.1 lower_bound 和 upper_bound两个基础积木用左闭右开模板来定义这两个操作最清晰lower_bound(nums, target)返回第一个“大于等于 target”的下标。upper_bound(nums, target)返回第一个“大于 target”的下标。有了它们所有重复元素相关的问题都能直接推需求表达方式第一个等于 target 的位置lower_bound(target)再验证该位置值是否等于 target最后一个等于 target 的位置upper_bound(target) - 1target 在数组中出现的次数upper_bound(target) - lower_bound(target)小于 target 的元素个数lower_bound(target)大于 target 的元素个数size - upper_bound(target)这五个结论背下来胜过背十个孤立的二分模板。4.2 手写实现只有一行条件不同用左闭右开模板两个操作只有判定条件的区别// 第一个 target 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; } // 第一个 target int upperBound(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; }注意观察lowerBound的条件是 target时向右upperBound的条件是 target时向右。差别就一个等号但语义完全不同。这也解释了为什么用统一模板比记三个独立模板好——你只需要记住“满足条件就收拢哪一侧”这一个动作剩下的全是机械替换。4.3 和 C 标准库对照一下C 的algorithm里就有std::lower_bound和std::upper_bound用法和上面手写的语义一模一样只不过作用于迭代器。如果你日常工作用 C我反而建议先搞懂上面手写版本再去用标准库——因为标准库接口隐藏了太多细节出了问题你连怎么调试都不知道。反过来能手写之后再看std::lower_bound(begin, end, value)你会觉得它毫无神秘感返回值就是“如果插入 value数组保持有序时它应该被插入的位置”。5. 二分答案把“求最值”变成“判断行不行”如果说边界查找是二分的第一层应用那“二分答案”就是第二层也是算法竞赛和面试中区分“会写二分”和“理解二分”的分水岭。5.1 为什么这么多个最值问题都能用二分求解直觉上二分只能处理“有序的东西”但“答案的值域”天然就是有序的。假设题目要求“求某个量的最小值”而这个量满足如果答案 X 可行那么所有大于 X 的值也可行。于是可行解构成一个从某个位置开始直到无穷大的区间答案就是这个区间的左端点。这不又成了一个“找第一个可行位置”的问题吗这就是二分答案法的通用套路确定答案的取值范围[L, R]。写check(mid)回答“当答案是 mid 时是否可行”。根据check结果调整左右边界。循环结束后L或right就是满足条件的最优答案。这个打法的核心是你不再直接求解而是把求解转换成“拿着一个候选答案去验证”。验证通常比求解简单得多这也是它巨大的优势。5.2 经典案例把 n 个数分成 m 段最小化最大段和我拿一个最经典的例子走一遍完整流程。题目给定长度为n的正整数数组要把它顺序切分成m段连续的区间问所有切分方案中“区间和的最大值”最小是多少。第一步想清楚单调性。如果“最大段和不超过 X”是可行的那么“最大段和不超过 X1”当然也可行——因为你还是可以按同样的方式切。所以可行区间是[答案, ∞)我们要找的就是那个最左的可行点。第二步划定二分范围。下界可以取max(数组元素)因为每一段至少要包含一个元素最大段和至少是单个元素的最大值上界可以取sum(数组)因为把所有元素放一段时最大段和是整个数组的和。第三步写check(mid)。贪心地从左往右扫数组累加当前段的和一旦超过mid就新开一段。最后统计切出的段数是否不超过mbool check(vectorint nums, int m, long long limit) { int cnt 1; long long cur 0; for (int x : nums) { if (cur x limit) { cnt; cur x; } else { cur x; } if (cnt m) return false; } return cnt m; }第四步把check嵌进二分框架int splitArray(vectorint nums, int m) { long long lo 0, hi 0; // lo 初始为 max 元素hi 初始为 sum for (int x : nums) { lo max(lo, (long long)x); hi x; } while (lo hi) { long long mid lo (hi - lo) / 2; if (check(nums, m, mid)) hi mid; // 可行尝试更小的值 else lo mid 1; // 不可行必须增大 } return lo; }注意check里用的是“不大于 limit”所以limit越大越可能成功单调性方向是“可行往右”所以我们收缩hi找最小的可行值。整个流程里最难的部分不是二分本身而是想清楚“可行性的单调方向”——是先往左收还是先往右收完全取决于 check 的单调方向。5.3 浮点数二分的精度控制如果答案是浮点数比如“求方程的根精确到小数点后 6 位”二分的框架不变但有两个细节要特别注意。第一个细节是循环条件不能再用lo hi——浮点数的相等判断不可靠改成固定迭代次数比如跑 60 次因为 60 次能把区间长度压缩到初始范围的 2 的 60 次方分之一精度早就足够。第二个细节是输出时不要直接输出lo而是用printf(%.6f, lo)或cout fixed setprecision(6) lo控制格式否则可能被精度误差坑掉最后一个四舍五入位。我自己写浮点二分时的一个教训曾经贪省事用while (hi - lo 1e-7)作为循环条件结果在某次极限数据上因为 lo 和 hi 靠得太近导致浮点数减法精度丢失提前退出循环答案差了一位。后来统一改成迭代 100 次再也没出过事。浮点二分里固定迭代次数永远比阈值判断更可靠。6. PTA 函数题与真实场景实战热搜词里有“二分查找pta函数”说明很多朋友是在数据结构课程的 PTA 平台上初次正面遭遇二分的。我就先讲讲这道几乎人人都写过的 PTA 函数题再说说两道稍微进阶的变体题把这些年的常见错误一次性抖干净。6.1 教科书最常见的 PTA 函数题Position BinarySearch(List L, ElementType X)题目背景是浙大版《数据结构》的经典函数题。函数接口是Position BinarySearch(List L, ElementType X);其中List的定义大致是这样typedef int Position; typedef struct LNode *List; struct LNode { ElementType Data[MAXSIZE]; /* 下标从 1 开始存放元素 */ Position Last; /* 最后一个元素的下标 */ };这个题最大的坑不在二分本身而在数组下标从 1 开始。如果你习惯了从 0 开始的编码方式第一版很可能写出low 0然后越界访问Data[0]里面没有有效元素或者整个查找范围漏掉了下标 1 的那个元素。正确写法是Position BinarySearch(List L, ElementType X) { Position low 1, high L-Last; while (low high) { Position mid low (high - low) / 2; if (L-Data[mid] X) return mid; else if (L-Data[mid] X) low mid 1; else high mid - 1; } return NotFound; }这里的NotFound是题目预定义的宏通常是 0因为下标从 1 开始0 正好可以当“不存在”的哨兵。很多人在 PTA 上拿不到满分的点包括没处理空列表Last 0时循环不进入直接返回 NotFound这条其实没问题、把NotFound写成了-1导致和题目的宏定义不一致、以及忘记L-Last已经表示最后一个元素的下标而多减一。这些都是“审题细节”而非算法问题但丢分丢得比算法错误还冤。6.2 旋转有序数组里找最小值进阶题里很经典的一类是 LeetCode 153旋转过的有序数组比如[4,5,6,7,0,1,2]里找最小值。这种数组整体不是有序的不能直接套一个“找 x ”模板但它的“两段分别有序”蕴含了另一种单调性。关键观察是最小值把数组分成两段前半段每个元素都大于等于最后一个元素nums.back()后半段每个元素都小于等于nums.back()。换句话说以nums.back()为参照从前往后扫会得到一串T再加一串F或者全是F当数组没有旋转过。我们要找的就是第一个F的位置——这正是二分的用武之地。int findMin(vectorint nums) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] nums[right]) left mid 1; // 左段最小值在右侧 else right mid; // 右段最小值在左侧或就是 mid } return nums[left]; }这个题最常出的错误是拿nums[mid]和nums[left]比较来判断自己在哪一段。在有重复元素时这种比较会失效而和nums[right]比较则更稳。顺带说一句如果你面试时遇到“旋转数组里找 target”思路是类似的——先用二分定位最小值把数组“解旋”再对合适的那一段做标准二分花不了几行代码。6.3 二维有序矩阵的查找还有一个高频变体一个m x n矩阵每行从左到右递增且下一行的第一个元素大于上一行的最后一个元素整块其实就是一个拉平了的一维有序数组。一眼看穿本质后解法就是把它映射成一维坐标做一次二分bool searchMatrix(vectorvectorint matrix, int target) { int m matrix.size(), n matrix[0].size(); int left 0, right m * n - 1; while (left right) { int mid left (right - left) / 2; int x mid / n, y mid % n; if (matrix[x][y] target) return true; else if (matrix[x][y] target) left mid 1; else right mid - 1; } return false; }这个题想考的其实不是二分本身而是你能不能把“矩阵”还原成“一维数组”。很多所谓难题本质上就是在用各种方式包装同一个单调序列你一旦能识别出单调性解法就呼之欲出。7. 调试二分查找的完整方法不变式、边界清单与随机对拍二分查找代码太短静态检查看不出问题直接提交又总在边界上炸。我这里分享一套我一直在用的调试流程每一步都是这几年踩坑踩出来的。7.1 用不变式解释每一行代码所谓不变式就是“每次循环开始前一定成立的某个命题”。二分查找里最经典的不变式是答案一定在当前区间[left, right)内如果存在的话。你写的每一行代码本质都是在维护这个不变式。当程序出错时不要急着打印mid而是先问自己三个问题left的语义是什么它指向的元素满足什么条件right的语义是什么它指向的元素满足什么条件循环结束时left和right指向的位置是不是我想要的答案如果你能流畅回答这三个问题你的代码大概率是对的回答不上来那代码基本就是靠运气写的。我见到过的绝大多数二分 bug最后都能追溯到“语义不清”——比如right到底表示“可行区域右侧”还是“最后一个可行位置”这两种理解会导出完全不同的收缩写法。7.2 必测的边界样例清单我写完任何二分代码后都会至少跑一遍这个清单每个样例都手动算一遍期望结果样例期望空数组返回 -1 / 返回 0只有一个元素且命中返回 0只有一个元素且不命中返回 -1target 比所有元素都小返回 0lower_boundtarget 比所有元素都大返回 size所有元素都等于 target返回 0first equaltarget 出现在最左端返回最左下标target 出现在最右端返回最右下标别看这些样例简单二分 bug 十有八九就藏在这几种极端里。特别是“target 比所有元素都小/大”这两种很多模板会返回越界值或死循环测一次就能现原形。7.3 随机对拍暴力算法是二分代码的照妖镜如果你写的是竞赛题或者 PTA 函数题还有一个更高效的手段随机对拍。思路是写一个绝对正确但可能很慢的暴力版本然后在随机小数据上反复对比你的二分版本和暴力版本的结果。我常用的套路以 Python 为例import random def brute(arr, target): # 暴力找第一个 target 的位置 for i, x in enumerate(arr): if x target: return i return len(arr) def binary(arr, target): left, right 0, len(arr) while left right: mid left (right - left) // 2 if arr[mid] target: left mid 1 else: right mid return left for _ in range(10000): n random.randint(0, 20) arr sorted(random.randint(0, 10) for _ in range(n)) target random.randint(-5, 15) assert brute(arr, target) binary(arr, target), (arr, target)对拍一跑边界 bug 会在几秒内暴露得一干二净。这个方法不仅适用于二分任何算法题我都建议在提交前对拍一轮。人脑检查逻辑总有盲区暴力代码不会骗你。写到这里回头看这几年自己和二分打的交道最大的心得其实一句话二分查找不难在“找”难在“清晰地定义你的搜索空间和判定条件”。你如果能用一句话说清楚left和right各自代表什么、循环退出时答案在哪儿那么不管题目换成旋转数组、二分答案还是二维矩阵你都能顺手写对反过来如果只是背模板拼手速换个题目就原形毕露。建议你以后拿到任意二分题先花三十秒在纸上写下“这个问题的单调条件是什么、可行区间是哪一侧、答案落在哪一侧”再动手写代码。这套习惯比任何模板都值钱。