我曾不止一次在技术社区里看到有人问“二分算法不就是在一个有序数组里折半查找吗为什么我写出来的代码老死循环”这个问题的背后其实藏着一个很深的误解。二分算法确实起源于有序数组的查找场景但它真正的价值远不止“查一个数在不在”这么简单。它能用来逼近方程的解、在答案空间里搜索最优方案、甚至在看起来完全无序的数据上找到局部规律。很多人学了几年二分刷了不少题遇到变体仍然一头雾水问题大概率出在只背了模板没理解二分工作的底层逻辑。这篇文章不会只给你罗列几个模板而是想把二分算法从“查找工具”升级为“解题思维”的完整路径梳理清楚。我会从二分的本质出发讲清楚为什么它要求的底层条件是“单调性”而不是“有序性”然后给出整数二分、浮点数二分、二分答案这几类高频题型的固定套路和题解最后再聊几个我在实际刷题和面试中反复踩过的边界坑。无论你是刚开始学算法的入门者还是准备面试需要快速过一遍二分题型的求职者这篇文章应该都能帮你把“会写二分”变成“懂二分”。1. 二分查找的底层逻辑有序只是表象单调性才是灵魂1.1 从猜数字游戏看二分的核心机制我先问一个看起来很基础的问题如果我从1到100里随机选一个数字你每次猜一个数我只告诉你“大了”还是“小了”最少多少次能保证猜中答案是7次因为每次猜测都能排除一半的可能2^7128100。这个游戏完美展现了二分的核心机制——每一轮迭代都要让搜索空间减半。你可能会说这个道理太简单了谁不知道二分啊。但关键问题在于很多人做二分题时只记住了“折半”这个动作却忽略了“为什么可以折半”。猜数字游戏能够成立是因为“大了”和“小了”这两个反馈能明确告诉你正确答案在当前搜索区间的哪一侧。这个反馈的根基是什么是我给数字的规则和猜的过程之间存在一个单调关系数字越往右越大猜测值大于答案的条件在区间内是单调成立的。所以二分的本质其实是利用一种可比较的单调关系用一个简单判断代替全局搜索。这个理解一旦建立你就会发现二分能处理的远不止“从有序数组里找一个数”这一种情况。1.2 有序数组、抽象单调与“单调性”的真正含义如果搜索对象是一个升序数组那么“nums[mid] target”这个判断天然是单调的mid 越大nums[mid] 就越大判断结果从“成立”逐步变为“不成立”。这个性质保证我们每次可以安全地丢弃一半不可能存在答案的空间。但“单调”这个词可以很抽象。比如给定一个函数f(x)随着x增大f(x)单调递减我想找f(x) 0的根——这是浮点数二分的经典场景。给定一个“可行性判定函数”check(mid)其返回值从true渐渐变为false或反过来我想找最后一个true的位置——这是二分答案题型的核心。在一个旋转过的有序数组里我们找“最小值”或“目标值”利用的是数组在断点两侧分别有序这个性质——虽然整体不单调但局部存在单调段。所以当你面对一个疑似二分的题目时先不要急着写代码先问自己**存在一个判断条件能让我排除掉一半的搜索空间吗**如果想清楚了那这道题就一定可以用二分解决。1.3 非单调场景为什么不能二分以及“峰值问题”的启示很多初学者会走另一个极端看到什么题都想二分结果在非单调问题上栽了跟头。经典的例子是“在无序数组中找一个峰值元素”LeetCode 162。你可能觉得题目名字里有“峰值”不就是找最大值的变体吗但二分峰值题能成立靠的恰恰是局部单调性只要nums[mid] nums[mid1]峰值一定在右侧反之就在左侧。这个结论成立的前提是数组两端定义为负无穷它本质上是用相邻两个位置的局部大小关系缩小峰值的可能区间。但如果题目要求“在完全无序的数组里找一个等于 target 的数”你能二分吗不能因为没有任何一个判断能让你安全丢弃一半数据。这个反例说明二分不是银弹它的前提始终是某种形式的单调性或可比较的可排除性。2. 整数二分的边界工程三种区间模板与死循环的根源说完了原理我们进入最痛苦的实操环节——整数二分的边界处理。我见过太多人原理讲得头头是道一写二分就出不来了不是死循环就是返回错误下标要么在mid计算上溢出。2.1 闭区间模板[l, r]的标准写法与循环条件闭区间模板是最好理解、也最容易出错的写法。这里的l和r都指向可能成为答案的下标循环条件通常是while (l r)当l r时循环结束。标准查找代码长这样int binarySearch(vectorint nums, int target) { int l 0, r (int)nums.size() - 1; while (l r) { int mid l (r - l) / 2; if (nums[mid] target) return mid; else if (nums[mid] target) l mid 1; else r mid - 1; } return -1; }我遇到很多初学这个模板的同学会困惑一个问题为什么l mid 1而不是l mid原因很简单——如果nums[mid]已经不等于target了那mid这个位置就绝无可能是答案可以让它从搜索区间里“滚出去”。如果你写成l mid当l和r只差1的时候mid取到l而nums[mid]又小于target那l会被重新赋值为mid永远是同一个值循环就永远不会退出。这就是死循环最常见的一个来源。2.2 左闭右开区间[l, r)模板库函数为什么偏爱它[l, r)是 C STL 里lower_bound、upper_bound等库函数内部使用的区间表示。标准的查找左边界代码是这样的int lowerBound(vectorint nums, int target) { int l 0, r (int)nums.size(); // r 指向最后一个元素的下一个位置 while (l r) { int mid l (r - l) / 2; if (nums[mid] target) l mid 1; else r mid; } return l; // 第一个 target 的下标 }注意这个模板有四个使用要点r初始化为n而不是n-1搜索区间是[0, n)不包含r所以当l r时搜索区间为空。循环条件是l r不能用否则同样的逻辑会多跑一轮。当nums[mid] target时说明mid左侧包括mid都不可能是答案所以l mid 1否则r mid因为mid本身可能是答案。返回值l和r相等指向第一个不小于target的位置。这套模板的心智模型是答案总是“半开区间”的左端点。如果你做的是找“第一个坏版本”这类题比如 LeetCode 278你会爱上这种写法因为它天然不用考虑返回值到底是l还是r——它们相等。2.3 mid 计算与区间更新方向的选择一个必须记牢的结论我刷了上百道二分题后总结出一条血泪经验当区间只剩两个元素时mid的取整方向决定了你该用哪种更新策略这是大多数死循环的根源。具体来说如果mid l (r - l) / 2即向下取整那mid有可能会等于l当l 1 r时。如果此时某个分支写成l mid那么l永远不会前进死循环必然会来。安全策略是当mid向下取整时所有更新都写l mid 1和r mid当mid向上取整时即mid l (r - l 1) / 2更新写l mid和r mid - 1。这句话我建议你直接背下来它可以根治你80%的二分死循环。而mid l (r - l) / 2这个写法本身也要比(l r) / 2更安全因为后者在l和r都接近INT_MAX时会整数溢出这在真实生产环境里一旦触发就是硬 bug。2.4 三套模板的对照表快速定位该用哪一套我整理了一个对照表方便你在刷题时快速判断该套用哪个模板。场景区间写法循环条件mid 取整更新方式返回什么精确查找 target[l, r]l r向下lmid1rmid-1命中下标或 -1查找第一个 ≥ target[l, r)l r向下lmid1rmidl即左边界下标查找最后一个 ≤ target(l, r]或[l, r]变体l r向上lmidrmid-1l即右边界下标注意观察其实三套模板只是用不同的区间表示法去描述同一个二分逻辑。你不需要全部记住并熟练但至少要精通其中两套因为左边界和右边界这两类题用一套模板硬套往往会绕晕。3. 基础题型题解标准查找、左右边界查找与浮点数二分光讲模板还不行我带你把最常见的四类二分题目各自过一遍每一步都对应上面的某套模板你才能真正在键盘上写出来。3.1 标准查找数组中的目标值是否存在这是最简单的二分应用。LeetCode 704 就是原题。核心代码我已经在上一节给出了不再重复。这里我补充两个容易忽略的点第一注意nums.size()返回的是无符号数如果你直接初始化int r nums.size() - 1当数组为空时nums.size() - 1会下溢成一个巨大的正数导致访问越界。先判断空数组是必须的。第二循环结束后l和r的关系。使用l r模板时如果没找到 target最终的l指向第一个大于 target 的元素r指向最后一个小于 target 的元素。理解这个关系对后面做“搜索插入位置”这类题非常有帮助。3.2 查找左边界第一个等于 target 的下标LeetCode 34 要求你找到 target 在有序数组中的第一个位置和最后一个位置。左边界就是上一节lowerBound的精确版本——找到第一个大于等于 target 的位置后再判断这个位置的值是否等于 target。题解代码int findLeft(vectorint nums, int target) { int l 0, r (int)nums.size(); while (l r) { int mid l (r - l) / 2; if (nums[mid] target) l mid 1; else r mid; } if (l (int)nums.size() nums[l] target) return l; return -1; }这个写法本质上就是lower_bound的裸实现。很多同学用闭区间模板写左边界时总会在r mid - 1和r mid之间纠结用左闭右开模板就没有这个烦恼。这也是我强烈推荐你用[l, r)写边界类二分的原因。3.3 查找右边界最后一个等于 target 的下标右边界和左边界看起来是对称的但实现上一不小心就掉坑。我们要找的是“最后一个小于等于 target 的下标”代码这样写int findRight(vectorint nums, int target) { int l 0, r (int)nums.size(); while (l r) { int mid l (r - l) / 2; if (nums[mid] target) l mid 1; else r mid; } // l 是第一个 target 的下标所以 l-1 是最后一个 target 的下标 if (l - 1 0 nums[l - 1] target) return l - 1; return -1; }看起来就是左边界代码里把换成了对吧但恰恰是这个细微改动让返回值从l变成了l - 1很多第一次写的同学会在这里蒙圈。我建议你亲自在草稿纸上模拟一遍[1, 2, 2, 2, 3]找 2 的过程把每次l、r、mid的变化写下来体会一下l最终停在哪里。这样一遍手工推演顶过你记十遍模板。3.4 浮点数二分精度阈值与迭代次数怎么选浮点数二分和整数二分最大的差别是没有“相等”的概念mid和正确答案之间只有精度上的差距。你必须用一个足够小的阈值eps来判断已经收敛。经典例题是求平方根实现一个函数计算sqrt(x)返回浮点数。核心代码double sqrtBinary(double x) { double l 0, r max(1.0, x); // 注意 x 1 时平方根比 x 大 for (int i 0; i 100; i) { double mid (l r) / 2; if (mid * mid x) l mid; else r mid; } return l; }这里我用固定迭代100次取代while (r - l eps)的判断原因是固定迭代次数的收敛时间完全可预期并且在极端情况下不会因为eps选得太小而陷入死循环。100次迭代后的精度大约是初始区间 / 2^100远远超过任何浮点数位数。另一个新手很容易踩的坑是r的初始值。如果x 0.25平方根是0.5比x本身还大所以r直接取x会导致答案被排除在区间外。我把r设为max(1.0, x)就是为了覆盖这个边界。4. 二分答案模型把“求最优解”翻译成二选一判断题如果说前两节的内容是二分的“基本功”那这节才是二分的“高光时刻”。我强烈认为二分答案才是二分算法真正强大到值得被单独总结成章的原因。4.1 二分答案的思维模式转换二分答案解决的是这样一类问题求某个“最值”而这个最值本身满足单调性。比如“在 D 天内送达包裹的最低运载能力”“分割数组的最大值最小化”“砍树最少高度”等等。这类题型的通用解法是三句话二分答案——在答案可能的范围[l, r]内二分每次取mid当作“候选答案”。写判定函数check(mid)——判断“如果答案是 mid问题是否可行”。根据check的单调性缩小范围——如果check(mid)为 true说明 mid 可以再小/大一点否则只能往反方向调。这听起来抽象我拆成两个具体题带你走一遍。4.2 最大化最小值题型LeetCode 410 分割数组的最大值题目要求把数组分割成 m 段使得这 m 段各自和的最大值最小。求这个最小最大值。先做思维转换——“最大值最小化”天然是二分的活。为什么因为判断“能否让最大值不超过 x”是非常容易的我只要贪心地从左到右分段一旦当前段的和超过 x 就新开一段最后看总段数是否不超过 m 就行。判定函数核心代码bool check(vectorint nums, int m, long long limit) { long long sum 0; int cnt 1; // 至少有一段 for (int num : nums) { if (sum num limit) { cnt; sum num; } else { sum num; } } return cnt m; }在main里l取数组最大值因为每一段至少要包含一个元素r取数组总和所有元素分成一段时。如果check(mid)为 true说明“最大值 mid”是可达成的我们可以尝试更小的最大值于是r mid否则l mid 1。4.3 最小化最大值题型LeetCode 1011 在 D 天内送达包裹这道题和上一题几乎一模一样只是描述场景换了按顺序把weights里的包裹在 D 天内运完每天的运载量固定为cap求最小的cap。这里二分的对象是“每天运载能力”l取单个包裹的最大重量r取总重量。判定函数check(cap)就是模拟连续D天每天从数组里尽量多装看能否装完bool check(vectorint weights, int days, int cap) { int need 1, cur 0; for (int w : weights) { if (cur w cap) { need; cur w; } else { cur w; } } return need days; }这两道题之所以要放在一起讲是因为它们的判定函数完全是一个套路从左到右贪心扫描不满足“阈值约束”就另起一段/一天。刷多了你会发现这类题的难点从来不是二分本身而是判定函数里这个贪心逻辑写不写得对。4.4 判定函数设计的通用套路与复杂度分析归纳一下二分答案的判定函数设计有三个步骤贪心确定“段/组/份”的划分规则。扫描一遍输入统计需要多少段或能否完成。把统计结果和题目限制条件比较返回true或false。复杂度方面二分答案的整体复杂度 O(log(答案范围)) × O(check 函数复杂度)。答案范围通常是1e9log大约 30check 函数一次扫描是O(n)。所以最终一般是O(n log n)量级在n 1e5的题目里完全够用。这也是为什么这类题在竞赛和面试里出现频率极高——它考察的是“能否识别出单调性并用贪心验证”而不是什么高深的数据结构。5. 进阶变体与实战避坑旋转数组、二维矩阵与峰值查找基础打牢了我再带你见识几种会让新手直接懵掉的二分变体。这些题目不是纯粹的“有序数组查找”而是把二分的适用范围又往外推了一步。5.1 旋转有序数组中的查找二分查找标准解法“旋转有序数组”指[4, 5, 6, 7, 0, 1, 2]这种由升序数组在某处旋转得到的数组。LeetCode 33 要求在其中搜索 target。核心思路是数组虽然整体不单调但每次二分后mid的左侧和右侧至少有一侧是严格单调的。我们可以通过比较nums[l]和nums[mid]的关系判断哪一侧有序再判断 target 在不在这一侧从而缩小范围int search(vectorint nums, int target) { int l 0, r (int)nums.size() - 1; while (l r) { int mid l (r - l) / 2; if (nums[mid] target) return mid; if (nums[l] nums[mid]) { // 左半段有序 if (nums[l] target target nums[mid]) r mid - 1; else l mid 1; } else { // 右半段有序 if (nums[mid] target target nums[r]) l mid 1; else r mid - 1; } } return -1; }这里的边界条件nums[l] nums[mid]注意有等号否则遇到数组长度为 2 的情况会出问题。这种题的实质是把“数据不是单调的”替换成“数据分段单调且已知分界特征”二分依然成立。5.2 二维矩阵二分先定位行还是直接二分整个矩阵LeetCode 74 是经典的“杨氏矩阵”变体每行升序且每行第一个元素大于上一行最后一个元素。最直接的解法是把二维矩阵按行拼接看成一个一维升序数组然后用下标映射二分int m matrix.size(), n matrix[0].size(); int l 0, r m * n - 1; while (l r) { int mid l (r - l) / 2; int val matrix[mid / n][mid % n]; if (val target) return true; else if (val target) l mid 1; else r mid - 1; } return false;这个技巧的价值在于二分不必真的把数组展开只需在下标转换上多做一个除法运算时间和空间都更省。当年我面试时第一次看到这个解法有种“原来二分还能这样玩”的顿悟感建议你也亲手写一遍体会一下。5.3 查找峰值元素无序情况下的二分也能用回到我开头提到的 LeetCode 162。数组无序但你只需要找到一个峰值且相邻元素不相等。用二分int findPeakElement(vectorint nums) { int l 0, r (int)nums.size() - 1; while (l r) { int mid l (r - l) / 2; if (nums[mid] nums[mid 1]) l mid 1; else r mid; } return l; }这个解法成立全靠一条局部单调性如果nums[mid] nums[mid1]说明mid处于上坡阶段那么峰值必然在mid右侧哪怕右侧整体不是单峰的至少能保证存在一个峰值否则峰值就在mid左侧或就是mid本身。这个结论不依赖全局有序只依赖“比较相邻元素能判断方向”这一点是一个非常好的“跳出有序数组”的二分思维案例。5.4 我在刷题中踩过的几个二分坑最后分享几个我在真实场景里踩过、后来反复提醒自己的坑。这些细节在教科书写得含糊但恰恰是面试官最喜欢深挖的角落。第一mid计算必须用l (r - l) / 2。这不是小题大做当l和r都是1e9级别时(l r)直接溢出成负数程序就会在数组下标上崩掉。哪怕是算法竞赛里常见的数据范围这一步也能帮你省掉至少半小时的调试时间。第二空数组和单元素数组一定要手动测一遍。我见过太多人代码逻辑没问题却被nums.size() - 1的整型下溢坑到怀疑人生。size_t到int的转换不是隐式安全的要养成先取长度并做一次越界判断的习惯。第三二分答案的l初始值务必根据题意确认好不要随手写成0。有些题目的答案不可能为 0比如运载能力至少是单件最大重量设成 0 并不会出错但会让判定函数多跑几次无意义的迭代而另一些题答案可以为 0你封死下界反而会答错。第四循环结束后想清楚l和r分别代表什么含义。用[l, r)模板时最后l r用[l, r]模板时最后l r且l指向第一个“大于目标”的位置。如果返回值需要进一步判断合法性比如检查是否越界、是否等于 target这一步千万不要省。第五如果你的二分进入了死循环先在草稿纸上把l、r、mid的演变写三轮。大多数死循环集中在区间长度为 2 时l或r没有收缩。对照我第 2 节给的“取整方向 更新方向”结论表基本可以一分钟内定位问题。每当有人问我说“二分这么简单有必要专门写几千字来总结吗”我都觉得他可能还没真正踏入过二分的深水区。从有序数组的标准查找到边界变体到二分答案模型再到旋转数组和峰值查找二分的每一次“变形”都在刷新我对它的理解。它教会我的最重要的事不是某个模板的写法而是寻找一种简单且单调的判断用它去裁剪看似复杂的问题空间。这种思维能力远比记住几个 API 和模板更有复利价值。希望这篇总结能让你也体会到这一点。