二分这个“老熟人”可能是很多人算法入门的第一个正儿八经的思路但也是我见过翻车率最高的基础算法。一提到二分大多数人的第一反应就是“有序数组里找一个数”然后背个模板就完事了。可等到真正上手做题尤其是碰到蓝桥杯、PTA或者笔试里的“最小值最大化”“最大值最小化”这类题却经常不知道该从哪里下手甚至写出了死循环还一脸懵。这篇文章会把“二分”当成一整套算法思想来拆而不是单纯讲查找。我尽量把原理、模板、边界处理、实战套路一次讲透顺手解决掉那些让你挠头的细节问题。无论是准备刷题的新手还是想在面试前把这个点彻底吃透的人都参考一下帮你少走点弯路。1. 二分到底在解决什么问题1.1 从“猜数字”到“可行性判断”很多人了解二分查找是从一个经典游戏开始的心里想一个1到100之间的数问几次能猜中答案是最多7次。这个游戏的每一步都在做同一件事——猜一个中点然后根据“大了”还是“小了”砍掉一半的候选范围。整个过程中你不需要关心最终答案具体是多少真正有用的信息其实只有两个词可行还是不可行。二分查找这一具体算法只是这套思想最直白的一个壳。掌握二分思想的标志是你看到一段有序序列时能想到用中点去试探而真正的应用场景要宽得多——你能给某个“答案”定义出“是否可行”的判断规则并且这个规则存在单调性那就能二分。这也是我把这篇博客定位为“算法思想”而不是“算法模板”的原因。二分查找是做选择题有确定目标值给你比对大小二分答案是做判断题不断给一个答案去验证行不行。前者是后者的一个特例但两者共用同一副骨架。搞懂了骨架你就能理解为什么有些题乍一看和二分八竿子打不着最后却能用二分解得漂亮。1.2 单调性才是二分的灵魂如果给二分思想找一个关键词我会选“单调性”而不是“有序”。我们说数组必须有序才能二分查找本质上是因为有序数组保证了下标和数值之间呈单调关系下标越靠后值越大或越小。二分每次通过中间点判断目标在左还是在右依赖的就是这个规律。现实中的题目往往不会直接给你一个排序好的数组。你要找的是“某个答案是否可行”而这个可行性和参数之间的单调关系很多时候需要你自己挖掘。举个例子给你一根长10米的木头问切成k段每段最长能多长。把每段长度从0往上枚举段数会单调递减——长度设得越大能切出来的段数只会变少或不变绝不会变多。这就是可以用来二分的单调性。事实上不只是二分查找和二分答案很多优化问题的解法和单调性都脱不开关系。比如四边形不等式优化DP里用的“决策单调性”本质上就是让候选决策点随着DP状态单调右移再利用二分去定位转移点把复杂度降一个量级。可见二分这台发动机的燃料就是单调性有没有那个“有序”的外表并不重要。1.3 见到什么信号该想到二分我们做题时最难受的就是看到题目不知道用什么方法。其实二分场景有很多典型信号题目要求“最大化最小值”“最小化最大值”“求满足某条件的最大/最小可能值”答案范围是一个连续区间且你不好直接算出来但给定一个候选值后能写出高效的check函数去验证一些解法中你面临在海量候选值里的暴力枚举且线性枚举必然超时。举个经典场景给一堆石头要你搬走若干块使得剩余石头之间的最小间距尽可能大。求这个最小间距的最大可能值。如果你是直接贪心要考虑“搬哪几块、总共搬多少”组合爆炸极其痛苦。但如果你换一个角度先假设间距是d再去判断“在保留间距至少为d的前提下能不能办到”一下子就好办多了。判一次d是否可行只要一趟扫描。既然判断单个d的代价很低那就从d的取值区间里去二分搜索最大的可行d。这是典型的“答案区间可枚举、直接构造答案困难、验证单点可行性容易”的题目一见这种组合就该条件反射地想到二分答案。顺带提一个常见误区很多人一提到“大范围搜索”就只会写暴力枚举或者DFS。二分不是暴力的替代品而是暴力的进化版。你从暴力枚举每一个可能答案进化成只枚举整数倍的中点每一次用check把大量候选区间丢弃本质上就是把一个O(n)的过程压缩成O(log n)。这个思维转变比会写任何具体模板都要值钱。2. 二分查找的三种经典写法2.1 闭区间写法最朴素也最易错的模板最经典的二分查找模板是用两个指针分别指向数组的左右边界且左右边界都被包含在搜索范围内。标准写法是初始化left0rightn-1循环条件是leftrightmid取(lr)//2判断中间值和目标的关系后更新leftmid1或rightmid-1。def binary_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这套模板看起来简单却暗藏两个最容易错的点。第一mid的计算最好写成left (right - left)//2而不是(leftright)//2。当数组长度接近int上限时left和right相加可能溢出虽然很多现代语言会自动升级类型但C等语言里溢出是实打实的风险。第二leftmid1和rightmid-1这两个更新方向不能乱改。如果左边界更新前已经是mid而mid又指向已经排除过的位置那就会重复访问进而引发死循环。我早年在面试里见过有人把更新写成leftmid导致两个指针永远指向相邻位置结果mid永远等于left于是left原地踏步循环永不退出。这在闭区间模板里是特别容易出的毛病很多人背模板时根本不去想这里为什么是1或-1。2.2 左闭右开写法让STL告诉你为什么这么写C的标准库里lower_bound和upper_bound这两个函数背后用的就是左闭右开区间也就是搜索范围是[left, right)循环条件是leftrightmid落在区间内部某个位置。这种写法的好处是和STL的区间概念完全一致不容易出现指针等于边界时语义混淆的问题。int lower_bound(vectorint nums, int target) { int left 0, right nums.size(); while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { right mid; } else { left mid 1; } } return left; }注意这套模板在更新右边界时用的是rightmid不是rightmid-1因为右端点本身不包含在搜索区间内。如果你把它当作闭区间来理解会觉得它明明还包含mid位置却舍弃了小白很容易绕晕。但一旦接受“右端点永不入界”这个设定它反而会比闭区间更顺手你只需要盯住“mid是候选答案还是该被排除”剩下交给固定的半边更新方式即可。我对这种写法的评价是一旦熟悉它比闭区间更不易错因为判断条件的空集情况天然被排除。很多人在LeetCode上做“寻找旋转排序数组中的最小值”这类题时遇到index越界根源往往就是使用了闭区间却忘记rightn-1和rightmid-1的组合会让区间过早变空。换成左闭右开这类边界错位几乎消失。2.3 找边界值lower_bound 和 upper_bound实际做题里你很少只需要判断“某个值是否出现”更多时候要找到“第一个大于等于target的位置”和“第一个大于target的位置”也就是lower_bound和upper_bound。找到这两个位置等于拿到了目标值在数组里的完整区间。统计重复元素个数、查找插入位置、求解“最接近target”这类问题全都能在一趟二分里解决。def lower_bound(nums, target): left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: right mid else: left mid 1 return left def upper_bound(nums, target): left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: right mid else: left mid 1 return left这里的关键是理解nums[mid]target和nums[mid]target这两个判断条件分别决定了中点位置归属哪一侧。查找第一个不小于目标值时等于目标的情况也不能返回必须继续向左压缩右边界保证返回的是最左的那个。查找第一个大于目标值时等于目标的情况要向右压缩左边界跳过所有相等项。这种写法和C标准库语义一致也算是我个人推荐的主力写法。原因很简单二分查找最怕的就是“找到了”但找错位置尤其是要求返回左侧或右侧边界的题目。lower_bound和upper_bound把边界语义固定下来从源头规避掉模棱两可的情况任何含重复元素的数据结构都不会把你绕晕。3. 二分答案从查找数据到解答问题3.1 把最优化问题翻译成判定问题如果说二分查找是在一组数据里找一个确定目标那二分答案则是在一个巨大的答案区间里猜最合适的那个值。翻译的方法是把“求某值最大/最小”的优化问题改写成“给定一个候选值判断它是否可行”的连续判定任务。这个改写越顺手你就越算正式跨进了二分思想的大门。以“分巧克力”这道经典蓝桥杯题为例有若干块矩形巧克力要实现切出k块边长相同的正方形求最大边长。直接想边长和怎么切你头脑会很快被可能的分割方案淹没。但如果你随便猜个边长c然后从每块巧克力上算一算能分割出多少个c×c的小正方形把总数加起来和k比一比瞬间就有了结论。c越大分出来的块数只会越少可行性随c的增大单调递减。于是问题变成在区间[1,最大边长]上二分搜索那个“还能满足总数≥k”的最大c。再举一个“带权二分”的典型应用。有些涉及DP的问题在转移时附带单位代价最优解会随代价权重偏斜。这时可以二分这个权重把原问题转化为一个“用辅助惩罚项修正”的判定问题从而找到满足平衡条件的最优解。二分答案在这里不直接查找最终结果而是搜索一个外部参数来指导DP转移起到调节天平的作用。我觉得记住一句话就行二分答案不是去找答案本身是去找“可行域和不可行域之间的那道墙”。从左往右前面一串都是可行的某一点之后全是不可行的你要找的就是最后一个可行点或第一个不可行点。只要你找到了这堵墙答案自然就在墙头。3.2 check函数的质量决定二分的上限在二分答案流程里二分本身的复杂度只有O(log n)真正耗时的大头几乎是check函数。很多题的难点也在check函数怎么写。我总结过三点在写check时特别管用。第一check的返回值必须严格符合“可行/不可行”的二元语义不要用模糊的“差不多”。“可行”要有明确定义——是段数够是距离够是重量不超再复杂的辅助操作都要落到这个binary的结果。第二check内部的计算过程要防溢出和防负值尤其是涉及乘法、总和或者取模的场景很多新手的check函数看似逻辑对但一跑就卡在中间某一步的越界或溢出上。第三如果check过程中能提前确定结果就直接返回别把整个数组跑完比如找跳石头题里一旦发现需要搬走石头数量已经超过限制立刻返回false可以省掉大量无用功。def check(c): count 0 for w in woods: count w // c if count k: return True return False这段代码来自“切木头”题。这里的count累加一旦达到k就提前返回避免无用的遍历。这也是check函数最常见的实用写法——一旦可行就直接短路返回省时省力。check函数本身往往只负责一件事计算给定c值下的某个属性值再和门限比较。从实战角度说check函数越简单二分越不容易出错。如果发现check里写了大量分支和状态变换你得警觉要么是问题理解不透要么是改成二分答案的时机未到。复杂的check本身没有错但查错难度会成倍上升笔试时间紧张时你不会有那个耐心去逐行调它。3.3 整数二分和实数二分的取舍二分答案在题目里遇到的基本有两种取值范围整数区间和实数区间。整数二分的更新靠leftmid1或rightmid-1循环条件用leftright或leftrightmid计算用整除。关键是让每一次循环都让区间长度严格减少防止死循环。这也是早前讲过的闭区间模板里mid和两侧更新的方向要匹配。实数二分的循环条件则有所不同最常用的两种做法是固定迭代次数比如100次直接写while(iter--)不用关心精度问题或者用while(right-lefteps)判断区间宽度当宽度小于精度阈值时停止。相比之下我更推荐固定迭代次数的写法。原因很朴素不管答案的规模多大、精度要求多高double的表示范围是有限的100次迭代已经把区间宽度缩到了2的100次方分之一这在绝大多数题目里早就超过精度要求。用eps时反而容易因为精度阈值设大设小而反复微调换题还可能失效。比如求一个函数的最大值或最小值范围在0到1e9之间精度要求1e-6。固定迭代100次后区间长度只剩约1e9除以2的100次方约等于0。这种稳定性要比你费心想个合适eps省心得多。实操中凡是精度题目我一律写100次迭代脑子里再不用为浮点比较头疼。唯一要注意的是浮点输出的格式控制保留小数位数要依据题意来别被默认的六位坑了。4. 边界处理的坑与死循环排查4.1 为什么你的二分会死循环二分代码看着简单死循环起来却也格外丢人。最常见的死循环成因是mid的计算取整方向和区间更新方式不匹配。我用一个具体场景来演示当前left0right1如果要找的是右边界你写了一个mid(leftright)//2算出mid0然后逻辑命中“向右走”把leftmid更新导致left还是0永远循环。另一个高频错误是把“闭区间”写法和“左闭右开”更新方式混搭。左边用闭区间的初始化left0,rightn-1右边却套用左闭右开的更新rightmid结果right永远指不到真正的右边界循环里mid范围反复横跳区间很快变成非法状态但循环继续跑最终越界或者死循环。这两种错误的病根都是mid取哪个方向向下取整还是向上取整必须和“区间缩小时期望保留哪些元素”保持一致。排查死循环我有一套固定套路。第一步把循环的入口条件打印或者手算几个中间状态观察left和right是否在缩小。第二步重点是看leftmid还是leftmid1、rightmid还是rightmid-1的语义有没有被严格遵守。理论上来说每一次循环后区间长度都应该严格变小如果某次更新后两个指针没有任何变化那死循环就板上钉钉了。第三步直接换成左闭右开模板重写等于换一套思维模式来检查逻辑很多时候比盯着代码找半天快多了。4.2 典型边界错误速查表我把这么多年看到过、踩过的高频二分错误汇总成一张表排错时对照着看效率很高。错误类型错误写法或思路正确做法溢出mid(leftright)/2用midleft(right-left)//2或位移写法死循环更新leftmid但mid取向下取整left不动更新为leftmid时改用向上取整mid(leftright1)//2越界左闭右开写rightn-1却更新rightmid用rightmid时初始化rightn答案错位lower_bound返回的是第一个大于等于target的位置误当target位置用先明确要找的位置语义再对号入座实数精度超时eps设得太小导致循环过多固定迭代100次判断条件反向把“需要更多”和“需要更少”搞反先画单调性示意图标注可行域方向等号导致死循环nums[mid]target时让leftmid1跳过目标找左边界时等号应该压缩右边界而非左边界这里最值得展开说一下的是lower_bound场景里的等号处理。很多人一看到等于target下意识返回mid这在不存在重复元素时没问题但重复元素一多就错。正确找第一个等于target的位置的方法是等号出现时继续压缩右边界找最后一个等于target的等号出现时再压缩左边界。等号的归属直接决定返回值是哪一侧也直接决定是否会漏掉目标。4.3 中值取整方向的记忆方法关于mid取整其实不需要死记硬背也不应该靠背模板硬套。我用一个很直观的记忆法如果你希望“未来的搜索区间偏向右边”也就是要找右边界、尽量把可行中点往右找那mid就得向上取整。反之如果你在找左边界、希望搜索过程偏向左侧mid就取向下取整。为什么会有这种对应关系因为mid向下取整时中点天然偏向left。若这时更新leftmidleft不会前进死循环风险最大而如果更新rightmid-1right会老老实实左移不会卡死。向上取整时mid偏向right反过来更新rightmid时right不会后退。所以记住一句话mid偏向哪一侧哪一侧的更新就不能是mid本身得稍微收缩一下或保证区间必然缩短。举个例子求“最小的可行值”模板通常写成下面的样式。left, right min_value, max_value while left right: mid left (right - left) // 2 if feasible(mid): right mid else: left mid 1 return left而求“最大的可行值”因为要找右边界要把mid改造成向上取整。left, right min_value, max_value while left right: mid left (right - left 1) // 2 if feasible(mid): left mid else: right mid - 1 return left这两套代码非常对称几乎可以做经典模板来背。核心就是找左边界的模板用mid往下取整找右边界的模板用mid往上取整。这样就不会出现 左边界模板leftmid 导致原地踏步的情况。我发现很多人之前背的都是闭区间模板一旦换成这种非严格的leftright循环思维会短暂混乱。但只要用几次之后你会明显感觉到边界处理比以前利索得多。5. 经典题目实战拆解5.1 蓝桥杯“跳石头”最大化最小值的思路“跳石头”是我在算法题里见过最能检验二分答案理解程度的一道题。它的描述简单到离谱河流里有若干块石头运动员要从起点跳到终点现在要搬走M块石头问搬完后最短跳跃距离的最大值是多少。难点不在于代码而在于你是否能想到“二分答案”这四个字。按二分答案的思路我们二分的是“最短跳跃距离”假设当前猜的值是mid。接下来要判断如果要求任意相邻落脚点的距离都不小于mid那最少要搬走多少块石头。判定方法有很多种我常用的贪心写法是遍历所有石头记录上一个保留石头的坐标如果当前石头和上一个保留石头之间的距离小于mid就搬走当前这块否则保留它并更新上一个保留位置。最后统计被搬走石头的总数是否小于等于M。是则mid可行说明还能尝试更大的距离否则就缩小。def check(d): removed 0 last_pos 0 for stone in stones: if stone - last_pos d: removed 1 else: last_pos stone return removed m这道题的核心是理解“最小的最大”为什么可以二分距离d越大需要搬走的石头越少可行性单调递减。只要你能写出这个check二分主体几乎是同一套骨架。整个题目最大的坑反而在check中的贪心策略——如果贪心策略写错比如应该在距离过小时搬后一块而不是当前块check的结果就会偏离真实二分自然也会解错。建议每次写check前先在草稿纸上把贪心模拟一遍再落笔成代码。5.2 PTA函数题二分查找的隐蔽边界PTA上有一类很经典的二分查找函数题要求在数组中找到元素并返回其下标但这个数组的索引从1开始编号。很多人拿常见的从0开始的模板往上套结果边界直接错乱尤其当目标值在第一个或最后一个位置时。这类函数题的核心约束是你写的函数只负责返回结果外部调用已经知道数组长度n和目标值。于是你初始化left1rightn循环条件用leftright即可。如果用了左闭右开模板right就要初始化成n1。这种小差异在本地测试不报错但一提交到PTA就疯狂报错原因就是左右边界的物理意义没有和题目一致。int search(int array[], int n, int target) { int left 1, right n; while (left right) { int mid left (right - left) / 2; if (array[mid] target) return mid; if (array[mid] target) left mid 1; else right mid - 1; } return -1; }另外一个容易错的地方是“如果存在多个相同元素返回任意一个即可”还是“返回最左侧那个”。PTA有些题不要求这一点但面试时这往往是区分你懂不懂lower_bound分界的重点。建议你在做这类题时主动想想如果要求返回最左出现的下标你的代码需要如何改动。把这个细节想通很多工程里二分查找的边界问题基本就出不了大乱子。5.3 “最大值最小化”模型的经典例子在二分答案题型中“最大值最小化”是与“最小值最大化”对称的另一大金刚。典型题目是给定一个数组要求把它分成连续的M段使得每段的和的最大值尽可能小。这个问题本身是DP也能做的但二分答案的思路更直观。我们二分一个候选值mid判断它是否可行就看“如果限制每段和不超过mid最少能分成多少段”。检查方式很经典从左往右贪心累加只要当前段加上下一个元素还没超过mid就继续加一旦会超过就新开一段。如果最少分出的段数小于等于M说明mid这个限制可行尝试更小的值否则说明mid太小所有段都会挤爆必须加大。def check(limit): segments 1 current_sum 0 for v in nums: if current_sum v limit: segments 1 current_sum v else: current_sum v return segments m这个贪心的正确性很好理解要尽量少分段每一段就该尽量多装如果连这种最紧凑的分法都超过M段那换成任何其他分法只会更多。它和二分答案组合起来就是一套非常标准的“最大化最小/最小化最大”处理流程。把这个模型吃透你会发现很多给数组分段、给任务分配资源的问题都是它换了一张皮。6. 实战中的经验技巧与算法延伸6.1 二分和其他算法的组合玩法二分答案真正的威力往往在于它能和其他算法拧成一股绳。最常见的是二分贪心类似上面跳石头和分段问题。再往深一层走还有二分DP、二分图论检边、二分网络流之类的组合。这类题的出现背景也非常自然如果直接求最优解很难但枚举一个可能答案之后用现成的经典算法来验证可行性会轻松很多。比如DP优化里的“带权二分”就是在DP转移代价中引入一个惩罚项通过二分惩罚系数来逼近原始问题的约束条件。这要求你会写DP也会二分是一种进阶玩法。再比如二分图论的典型应用求“使得图中路径上最大边权尽量小的生成树”先二分边权上限再用并查集或DFS判断图是否连通。check内层使用图论算法外层跑二分复杂度从一次图的构建降到了log级别的多次构建。我个人的建议是先把二分贪心玩熟再到二分DP和图论里尝试碰撞。不用一上来就啃最难的题否则很容易因为check函数写不出来而怀疑自己是否真的理解了二分。一旦你体会到“外层二分、内层算法”的节奏感之后见到很多带“最大值最小/最小值最大”字样的题你一眼就能看穿结构。6.2 六个提升效率的二分编码技巧在日常写代码时有几个二分相关的编码细节能明显提升你的效率和正确率。第一所有用到的区间边界一律使用变量名left/right而不是l/r语义清晰不说排查问题时能少想好几秒。第二mid统一写成left(right-left)//2或者(right-left1)//2和left配合加1的写法永远不要写成(leftright)//2来贪图省事。第三所有二分答案的循环条件都用leftright配合方向匹配的更新这是最不容易出错的组合。第四在while循环体内不要多次计算mid条件一次算出后存进变量后面直接用。第五对于实数二分我前面说过直接固定迭代100次或者取精度和范围匹配的固定次数就行不要写eps然后调来调去。第六养成给check函数单独写小测试的习惯——最少测一个边界情况比如mid取到区间最小值时应该返回什么mid取到最大值时又应该返回什么。这些小技巧看似琐碎实际能在紧张的笔试中帮你节省出很多试错时间。我见过不少人在正式比赛里因为mid取整方向写错然后一路查bug最后什么都来不及。如果你平时就把模板焊死了根本不会踩这种低级错误。6.3 二分练习路线与难度分级练习二分不需要堆题海但需要有层次地刷。我觉得一个比较合理的路线是先刷纯二分查找类比如LeetCode上的二分查找基础题、搜索插入位置、在排序数组中查找元素的第一个和最后一个位置。这些题帮你夯实模板尤其是lower_bound和upper_bound的边界语义。第二个层次是做二分答案类的基础题比如蓝桥杯的分巧克力、切绳子、跳石头PTA上的公路村村通这种带检查性质的题。重点训练从“求最值”到“判断可行性”的思维转换。第三层次可以挑战带复杂check函数的组合题比如最大化最小值加贪心、最大值最小化加DP、检查图连通性等。到这一层你才算真正把二分思想用活。刷题时建议准备一个错题本只记录二分的坑。比如哪个题是因为等号归属写错了哪个题是因为mid取整方向不对哪个题是为了精度调了半天eps。回头翻一翻你会发现自己犯过的错误其实就那么几类而这些恰是二分思想里最需要加强的地方。学算法很多时候就是这样一个把错误集齐再逐个击破的过程二分尤其如此。结尾说到最后其实二分给我印象最深的不是它能省多少时间而是它逼着你换一种提问方式。很多难题直接问“最优解是多少”你想破头也没思路但只要你把它改写成“给定一个答案验证它行不行”一切都豁然开朗。这种思维上的转换比记住几个模板值钱得多我推荐每个刷算法的人都在这个点上多花点时间。最后再分享一个小技巧如果笔试时时间紧张拿不准一个最值问题能不能用二分你就先写一个check函数再加上十几行的二分骨架如果逻辑顺下来感觉不别扭那基本就是二分题。多练几次你会慢慢培养出这种直觉到那时候二分就不再是背模板而是真正的武器了。