我曾不止一次在技术社区里看到有人问：“二分算法不就是在一个有序数组里折半查找吗，为什么我写出来的代码老死循环？”这个问题的背后，其实藏着一个很深的误解。二分算法确实起源于有序数组的查找场景，但它真正的价值，远不止“查一个数在不在”这么简单。它能用来逼近方程的解、在答案空间里搜索最优方案、甚至在看起来完全无序的数据上找到局部规律。很多人学了几年二分，刷了不少题，遇到变体仍然一头雾水，问题大概率出在：只背了模板，没理解二分工作的底层逻辑。
这篇文章不会只给你罗列几个模板，而是想把二分算法从“查找工具”升级为“解题思维”的完整路径梳理清楚。我会从二分的本质出发，讲清楚为什么它要求的底层条件是“单调性”而不是“有序性”，然后给出整数二分、浮点数二分、二分答案这几类高频题型的固定套路和题解，最后再聊几个我在实际刷题和面试中反复踩过的边界坑。无论你是刚开始学算法的入门者，还是准备面试需要快速过一遍二分题型的求职者，这篇文章应该都能帮你把“会写二分”变成“懂二分”。
1. 二分查找的底层逻辑：有序只是表象，单调性才是灵魂
1.1 从猜数字游戏看二分的核心机制
我先问一个看起来很基础的问题：如果我从1到100里随机选一个数字，你每次猜一个数，我只告诉你“大了”还是“小了”，最少多少次能保证猜中？答案是7次，因为每次猜测都能排除一半的可能，2^7=128>100。这个游戏完美展现了二分的核心机制——每一轮迭代，都要让搜索空间减半。
你可能会说，这个道理太简单了，谁不知道二分啊。但关键问题在于，很多人做二分题时只记住了“折半”这个动作，却忽略了“为什么可以折半”。猜数字游戏能够成立，是因为“大了”和“小了”这两个反馈，能明确告诉你正确答案在当前搜索区间的哪一侧。这个反馈的根基是什么？是我给数字的规则和猜的过程之间，存在一个单调关系：数字越往右越大，猜测值大于答案的条件，在区间内是单调成立的。
所以二分的本质其实是：利用一种可比较的单调关系，用一个简单判断代替全局搜索。这个理解一旦建立，你就会发现，二分能处理的远不止“从有序数组里找一个数”这一种情况。
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[mid+1]，峰值一定在右侧；反之就在左侧。这个结论成立的前提是数组两端定义为负无穷，它本质上是用相邻两个位置的局部大小关系，缩小峰值的可能区间。
但如果题目要求“在完全无序的数组里找一个等于 target 的数”，你能二分吗？不能，因为没有任何一个判断能让你安全丢弃一半数据。这个反例说明：二分不是银弹，它的前提始终是某种形式的单调性或可比较的可排除性。
2. 整数二分的边界工程：三种区间模板与死循环的根源
说完了原理，我们进入最痛苦的实操环节——整数二分的边界处理。我见过太多人，原理讲得头头是道，一写二分就出不来了，不是死循环，就是返回错误下标，要么在mid计算上溢出。
2.1 闭区间模板[l, r]的标准写法与循环条件
闭区间模板是最好理解、也最容易出错的写法。这里的l和r都指向可能成为答案的下标，循环条件通常是while (l <= r)，当l > r时循环结束。标准查找代码长这样：
int binarySearch(vector<int>& 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(vector<int>& 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 | 向下 | l=mid+1，r=mid-1 | 命中下标或 -1 |
| 查找第一个 ≥ target | [l, r) | l < r | 向下 | l=mid+1，r=mid | l（即左边界下标） |
| 查找最后一个 ≤ target | (l, r]或[l, r]变体 | l < r | 向上 | l=mid，r=mid-1 | l（即右边界下标） |
注意观察，其实三套模板只是用不同的区间表示法，去描述同一个二分逻辑。你不需要全部记住并熟练，但至少要精通其中两套，因为左边界和右边界这两类题，用一套模板硬套往往会绕晕。
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(vector<int>& 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(vector<int>& 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(vector<int>& 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(vector<int>& 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 函数复杂度)。答案范围通常是1e9，log大约 30；check 函数一次扫描是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(vector<int>& 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(vector<int>& 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[mid+1]，说明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 和模板更有复利价值。希望这篇总结能让你也体会到这一点。
