先说一个我自己的经历。某次维护老模块时，上游同学递过来一段不到二十行的二分查找代码，逻辑看着很顺，但测试一跑就卡住了——不是找不到值，而是目标值不存在时，返回的位置比预期偏右一格。我们花了一整个下午盯那几行代码，最后发现只是mid更新时少了一个加一。
二分查找就是这样一种算法。代码越短，越容易在细节上翻车，而且翻车的方式往往不是“找不到”，而是“找出来的位置不对”。这篇文章我打算围绕 C++ 里二分查找的真正难点来写：区间怎么定义，边界怎么更新，变体怎么推导，以及在旋转数组、矩阵、二分答案这些场景里它到底怎么变形。适合刚学完基本语法、准备刷题或写工程代码的人，也适合多年没碰二分、想一次性把边界想明白的老手。
1. 二分查找的本质：不是在搜值，而是在排除区间
很多人学二分查找，记住的第一句话是“数组必须有序”。这个说法不算错，但它掩盖了一个更本质的东西：二分查找每一步做的事情，不是“比较两个数相不相等”，而是通过一次比较，把当前搜索区间砍掉一半，并保证目标值仍然留在剩下那一半里。
想清楚这一点，再回头看你写的每一行代码就会顺很多：left和right不是两个普通变量，它们共同描述了一个“目标值可能存在”的区间。每次循环都要确保这个区间没有被错误地缩小，否则后面的一切都是白搭。
1.1 什么场景才配用二分
第一个判断标准是单调性。所谓单调，不只是数组里的数字从小到大排，还包括更广义的“判定结果单调”。比如“给定一个阈值x，判断方案是否可行”，如果x越大越容易满足，那这个判定函数就是单调的，就能在x的取值范围上做二分。
第二个判断标准是“一次比较能排除一半”。在某一步，你必须有办法知道目标不在某个半边。数组有序只是满足这个条件的最常见形式。例如旋转数组不是完全有序，但它分成两段，每段内部有序，所以仍然可以用二分，只是需要额外判断目标落在哪一段。
但要注意，并不是“沾了有序边”就一定能二分。比如一个数组里全是重复元素，要求返回第一个等于目标值的位置，这时候等值判断本身不可靠，你得把比较条件从==改成<，用 lower_bound 的思想来处理。这说明场景定了，比较关系才能定，顺序不能反过来。
1.2 两个区间模型：为什么 C++ 程序员必须分清
写 C++ 二分，第一行代码之前先回答一个问题：你维护的区间是“左闭右闭”还是“左闭右开”？
先看最常见的左闭右闭写法：
int binarySearch(const vector<int>& 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; }再看左闭右开写法：
int binarySearchOpen(const vector<int>& nums, int target) { int left = 0, right = nums.size(); // 注意这里不是 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; } } return -1; }两种写法都能跑，但背后的约定完全不同。左闭右闭意味着left == right时区间里还有一个元素，所以循环条件必须用<=；当你判断nums[mid]大于目标时，mid已经可以确定不在答案里，于是right = mid - 1。左闭右开则意味着right本身不参与搜索，循环条件用<，更新右边界时只需要right = mid，因为新区间天然不包含mid。
我见过最多的翻车现场，就是“心里想的是左闭右开，手上却写着左闭右闭的更新逻辑”。代码风格可以混，但区间定义不能混。写之前先在注释里写一句“当前答案在 [left, right] 中”，哪怕只是给自己看，也能少踩一半坑。
2. 手写二分最容易翻车的三个细节
基本模板看上去只有几行，可一旦开始改边界，问题就接踵而来。下面这三个细节是我在所有二分代码里最先检查的东西。
2.1 mid 的计算不只是防溢出
多数教材会告诉你，mid = (left + right) / 2在极端情况下会溢出，因为left + right可能超过 int 上限。更好的写法是mid = left + (right - left) / 2。这个写法不仅安全，还直观表达了取中点。
但更少人注意到的是取整方向问题。left + (right - left) / 2是向下取整。在while (left < right)这类循环里，如果某次更新变成了left = mid，一旦left和right相邻，mid就会等于left，此时left永远无法前进，直接死循环。解决办法一是把更新改成left = mid + 1，二是当你确实需要取右中位数时，用mid = left + (right - left + 1) / 2。
不要小看这一个取整方向。搜索旋转数组、求最后一个满足条件的元素，这类变体常常要用到右中位数。脑子里同时记住两套取整公式，写代码时会从容很多。
2.2 循环不变量才是边界公式的源头
很多人背下了全部模板，但换个场景就懵。因为模板不是记忆单位，“循环不变量”才是。
所谓循环不变量，是指每次循环开始前，你都能说出“答案一定在 [left, right] 中”这句话。举个具体例子：你要找一个数组里第一个大于等于target的下标，于是写下：
int lowerBound(const vector<int>& 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; }为什么条件写的是nums[mid] < target而不是nums[mid] >= target？因为我们的不变量是“答案下标落在 [left, right] 中”。如果nums[mid] < target，说明mid下标一定不满足“大于等于 target”，所以答案范围为[mid+1, right]，于是left = mid + 1。如果nums[mid] >= target，那么mid可能已经是答案，也可能答案在它左边，于是保留mid，让right = mid。
这套推导过程比任何模板都可靠。模板可能因为题型微调而过期，不变量不会。
2.3 循环退出后 left 和 right 意味着什么
标准二分查找中，while (left <= right)退出时left > right，这时-1被返回。但在 lower_bound 这类变体里，while (left < right)退出时left == right，这个位置本身就是答案的候选位置。
所以写变体时有个很好用的习惯：循环结束后，单独检查left位置上的值是否满足最终条件，再决定返回它还是返回-1。不要在主循环里硬塞太多==分支。等值判断加得越多，代码就越像分支怪物，越容易漏掉边界。
比如找“第一个等于 target 的下标”：
int firstEqual(const vector<int>& 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; } } if (left < nums.size() && nums[left] == target) return left; return -1; }这比“在循环里同时判断==、<、>”清爽太多，而且不会出现“找到了却又漏掉更早位置”的问题。循环退出后做一次检查，代价很小，心智负担却大幅降低。
3. 四个高频变体：从 lower_bound 到 upper_bound 再到“最后一次出现”
二分的变体题，其实都是围绕“返回位置”的细微差别展开的。把 lower_bound 和 upper_bound 吃透，之后写“第一个等于”“最后一个小于”这类函数基本都是套同一套推导。
3.1 手写 lower_bound：判定条件为什么是 <
C++ 标准库里已经提供了std::lower_bound，它的语义是“返回第一个不小于给定值的迭代器”。手写一遍，能帮助你理解库函数内部到底发生了什么。
int lowerBound(const vector<int>& 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; }注意，这里right的初始值是nums.size()，而不是nums.size()-1。因为“第一个不小于 target 的值”有可能落在数组末尾之外，比如 target 比所有元素都大，这时答案就是nums.size()。你把搜索区间的上界设成开区间，才把这个情况包含进去。
这也是为什么我一直强调“先选区间模型再写代码”。在这个函数里，左闭右开是最自然的选择，如果你的目标是“左闭右闭”，那返回逻辑和初始值又要换一套，很容易出问题。
3.2 upper_bound 与最后一次出现的位置
std::upper_bound返回“第一个大于给定值的迭代器”。手写版本只需要把判定条件反过来：
int upperBound(const vector<int>& 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 的位置：先求
lower_bound，检查该位置是否等于 target - 最后一个等于 target 的位置：先求
upper_bound，然后减一，再检查该位置是否等于 target - 小于 target 的元素个数：
lower_bound返回的下标 - 小于等于 target 的元素个数：
upper_bound返回的下标
用标准库验证手写结果是很好的训练方式。写完之后，在随机数据上用std::lower_bound和std::upper_bound做对比测试，如果结果不一致，说明你的边界推导有问题，而不是库有问题。这种对照测试能帮你快速定位逻辑漏洞。
3.3 变体题不需要背模板：用不变量推一遍
举个例子：给定有序数组，里面有重复元素，要求返回最后一个等于target的下标。如果你只是搜“二分模板”硬套，很可能写出一个“死循环版”。但我们用不变量来推：
目标是“最后一个等于 target 的位置”，那么每次循环后，答案应该在区间[left, right]中。当nums[mid] > target时，mid 太大，答案在左侧，right = mid - 1。当nums[mid] <= target时，mid 可能是答案，也可能答案在右侧，所以保留 mid，left = mid。这时你发现mid = left + (right - left) / 2会导致相邻区间死循环，所以要改成取右中位数：
int lastEqual(const vector<int>& nums, int target) { int left = 0, right = nums.size() - 1; while (left < right) { int mid = left + (right - left + 1) / 2; if (nums[mid] > target) { right = mid - 1; } else { left = mid; } } if (nums[left] == target) return left; return -1; }这里left = mid是关键，它要求取中点时“向上取整”。如果你不关心取整方向，这个题基本写不对。所以我的建议是：见到“找最后一个”“求最大值”这类场景，第一步就写下右中位数公式，不要等出 bug 了再回头改。
4. 当二分离开有序数组：旋转数组、矩阵与二分答案
二分查找的高级用法，是把“数组区间”抽象成“答案区间”。这一节我讲三个常见场景，每个都是二分思想的延伸，而不是新算法。
4.1 旋转排序数组的二分条件判断
一个原本升序的数组在某个位置旋转，比如[1,2,3,4,5]旋转成[4,5,1,2,3]。要在这个数组里找目标值，表面上不是全局有序，但旋转数组有个特点：把数组从中间切开，一半一定是有序的。
判断方式很简单：比较nums[mid]和nums[left]。如果nums[mid] >= nums[left]，说明左半段是有序的，否则说明右半段是有序的。接下来就判断 target 是否落在那一半有序区间内，决定往哪边走。
int searchRotated(const vector<int>& 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; if (nums[left] <= nums[mid]) { if (nums[left] <= target && target < nums[mid]) { right = mid - 1; } else { left = mid + 1; } } else { if (nums[mid] < target && target <= nums[right]) { left = mid + 1; } else { right = mid - 1; } } } return -1; }注意比较关系都是“闭区间套闭区间”，因为下标本身代表真实位置。如果数组里有重复元素，nums[left] <= nums[mid]的判断会退化，这时往往需要先让left++跳过重复边界，再做常规二分。这说明二分在数据重复时并非万能，它需要额外的摸索。
4.2 二维有序矩阵：是“展平”还是“逐行”
如果矩阵满足“每行从左到右递增，且下一行的第一个值大于上一行的最后一个值”，那可以直接把整个矩阵当作一个长数组做二分，只需要在取 mid 时做一次下标映射：
bool searchMatrix(const vector<vector<int>>& 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 val = matrix[mid / n][mid % n]; if (val == target) return true; if (val < target) left = mid + 1; else right = mid - 1; } return false; }但如果矩阵只是“每行递增，每列递增”，并无行间的大小承接关系，就不能直接展平。我曾在一个题里用“先定位行，再在行内二分”的思路，结果因为没考虑列方向，漏掉了跨行分布的情况。这种矩阵更适合从右上角或左下角出发，用排除法逐步缩小范围，每步可以排除一行或一列，虽然时间复杂度同样是 O(m+n)，但逻辑更贴合数据规律。
所以遇到二维题，先问清楚矩阵的组织方式，再决定采用哪种二分策略。看到“有序矩阵”四个字就套全局二分，是最容易踩的结构性大坑。
4.3 二分答案：把最优化问题变成判定问题
这类题型近年来很常见：比如“把数组分成 k 段，每个段的和有一个上限，问这个上限最小可能是多少”。直接求很难，但如果反过来“给定一个上限 mid，判断能不能在 k 段内完成”，就变得非常简单。这种“对答案本身二分，用判定函数决定缩上界还是缩下界”的思路，就是二分答案。
我写过的一个模板结构：
bool canPart(const vector<int>& nums, int limit, int k) { int count = 1; long long sum = 0; for (int x : nums) { if (sum + x > limit) { count++; sum = x; } else { sum += x; } } return count <= k; }主流程：
int splitArray(const vector<int>& nums, int k) { long long left = 0, right = 0; for (int x : nums) { left = max(left, (long long)x); right += x; } while (left < right) { long long mid = left + (right - left) / 2; if (canPart(nums, mid, k)) { right = mid; } else { left = mid + 1; } } return left; }这里的left初始值为数组最大值，right为数组总和，因为任何一个合法段的和都不可能小于单个元素最大值，也不可能大于总和。这个上下界构造非常重要，它决定了二分初始区间是否包含真实答案。
对“最大值最小化”和“最小值最大化”两类题，基本都能套这个套路。判定的单调性在于：限制越宽松，段数越少，越容易满足“段数不多于 k”。当限制从紧到松变化时，判定结果从 false 变成 true，这个临界点就是答案。二分的核心就是在找那个临界点。
5. 一次真实的死循环排查过程，以及我的自查清单
理论讲再多，都不如真刀真枪查一次 bug 来得深刻。下面这段代码，是我模拟某次线上问题时重构出来的，它看起来非常合理，但跑起来会卡死。
5.1 一份看似正确的 lower_bound 错在哪
int buggyLowerBound(const vector<int>& nums, int target) { int left = 0, right = nums.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid; // 这里应该是 mid + 1 } else { right = mid - 1; // 这里又把 mid 排除掉了 } } return left; }乍一看，left更新时保留 mid，看起来是“安全”的；right更新时排除 mid，又符合“答案偏左”的直觉。但问题出在组合逻辑上：当nums[mid] < target时，mid 一定不是答案，你却偏要保留它；当nums[mid] >= target时，mid 可能是答案，你又把它排除。这就是典型的“区间不变量不一致”。
为了演示，取nums = [1, 3, 5], target = 4：
- 初始 left=0, right=2, mid=1, nums[1]=3 < 4，走第一分支，left=1
- left=1, right=2, mid=1，仍 nums[1]=3 < 4，left=1，完全不变
于是死循环。
5.2 用可复现的方式揪出边界 Bug
排查死循环时，我从不靠肉眼反复读代码。死循环意味着某一步更新没有让区间缩小，最快的方法是打印出每一次的left、right、mid和比较结果。
while (left <= right) { int mid = left + (right - left) / 2; cout << "left=" << left << ", right=" << right << ", mid=" << mid << ", nums[mid]=" << nums[mid] << endl; // ... 分支 }日志一旦打出来，问题就藏不住了：你会看到 left 连续两次保持同一个值。接下来再用小数据手推，或者直接用随机测试和暴力函数对比，确认“到底哪一步违反了不变量”。
一个更系统的方法是写断言辅助验证：
assert(nums[mid] != nums[left] || left == right);这种断言在二分变体里很容易失效，因为它要求每一步都缩小范围。测试时把它打开，线上发布再关掉，能帮你把潜在逻辑错误尽早暴露。
5.3 二分写完之后的建议
结合我自身踩过的坑，整理了一份自查清单。每次写完二分，按这个顺序过一遍，基本能堵住绝大多数低级错误。
- 区间模型定了吗？
right初始值是size()还是size()-1？循环条件写的是<还是<=？ - 分支更新是否与区间模型匹配？左闭右闭时
right = mid - 1，左闭右开时right = mid，不能混写。 mid的取整方向是否与“是否可能执行 left = mid”匹配？只要出现left = mid，就用右中位数公式。- 循环退出后，答案位置是否一定有效？lower_bound 返回
size()时，后续访问下标前必须判空。 - 对象数组等复杂类型比较时，是否符合严格弱序？C++ 的
lower_bound默认用<，你手写版本也最好保持一致。
二分查找看似简单，却是面试、竞赛和工程代码里出错率极高的算法。它的核心从来不是背代码，而是把区间定义、循环不变量和取整方向这三样东西在动手前想清楚。希望这篇文章能帮你少踩几个坑，尤其是那种“看起来没问题，一跑却死循环”的诡异场景。
