先说一个我自己的经历。某次维护老模块时上游同学递过来一段不到二十行的二分查找代码逻辑看着很顺但测试一跑就卡住了——不是找不到值而是目标值不存在时返回的位置比预期偏右一格。我们花了一整个下午盯那几行代码最后发现只是mid更新时少了一个加一。二分查找就是这样一种算法。代码越短越容易在细节上翻车而且翻车的方式往往不是“找不到”而是“找出来的位置不对”。这篇文章我打算围绕 C 里二分查找的真正难点来写区间怎么定义边界怎么更新变体怎么推导以及在旋转数组、矩阵、二分答案这些场景里它到底怎么变形。适合刚学完基本语法、准备刷题或写工程代码的人也适合多年没碰二分、想一次性把边界想明白的老手。1. 二分查找的本质不是在搜值而是在排除区间很多人学二分查找记住的第一句话是“数组必须有序”。这个说法不算错但它掩盖了一个更本质的东西二分查找每一步做的事情不是“比较两个数相不相等”而是通过一次比较把当前搜索区间砍掉一半并保证目标值仍然留在剩下那一半里。想清楚这一点再回头看你写的每一行代码就会顺很多left和right不是两个普通变量它们共同描述了一个“目标值可能存在”的区间。每次循环都要确保这个区间没有被错误地缩小否则后面的一切都是白搭。1.1 什么场景才配用二分第一个判断标准是单调性。所谓单调不只是数组里的数字从小到大排还包括更广义的“判定结果单调”。比如“给定一个阈值x判断方案是否可行”如果x越大越容易满足那这个判定函数就是单调的就能在x的取值范围上做二分。第二个判断标准是“一次比较能排除一半”。在某一步你必须有办法知道目标不在某个半边。数组有序只是满足这个条件的最常见形式。例如旋转数组不是完全有序但它分成两段每段内部有序所以仍然可以用二分只是需要额外判断目标落在哪一段。但要注意并不是“沾了有序边”就一定能二分。比如一个数组里全是重复元素要求返回第一个等于目标值的位置这时候等值判断本身不可靠你得把比较条件从改成用 lower_bound 的思想来处理。这说明场景定了比较关系才能定顺序不能反过来。1.2 两个区间模型为什么 C 程序员必须分清写 C 二分第一行代码之前先回答一个问题你维护的区间是“左闭右闭”还是“左闭右开”先看最常见的左闭右闭写法int binarySearch(const 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; }再看左闭右开写法int binarySearchOpen(const vectorint 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 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; }为什么条件写的是nums[mid] target而不是nums[mid] target因为我们的不变量是“答案下标落在 [left, right] 中”。如果nums[mid] target说明mid下标一定不满足“大于等于 target”所以答案范围为[mid1, 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 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; } } 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 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; }注意这里right的初始值是nums.size()而不是nums.size()-1。因为“第一个不小于 target 的值”有可能落在数组末尾之外比如 target 比所有元素都大这时答案就是nums.size()。你把搜索区间的上界设成开区间才把这个情况包含进去。这也是为什么我一直强调“先选区间模型再写代码”。在这个函数里左闭右开是最自然的选择如果你的目标是“左闭右闭”那返回逻辑和初始值又要换一套很容易出问题。3.2 upper_bound 与最后一次出现的位置std::upper_bound返回“第一个大于给定值的迭代器”。手写版本只需要把判定条件反过来int upperBound(const 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 的位置先求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 可能是答案也可能答案在右侧所以保留 midleft mid。这时你发现mid left (right - left) / 2会导致相邻区间死循环所以要改成取右中位数int lastEqual(const vectorint 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 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; 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 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 val matrix[mid / n][mid % n]; if (val target) return true; if (val target) left mid 1; else right mid - 1; } return false; }但如果矩阵只是“每行递增每列递增”并无行间的大小承接关系就不能直接展平。我曾在一个题里用“先定位行再在行内二分”的思路结果因为没考虑列方向漏掉了跨行分布的情况。这种矩阵更适合从右上角或左下角出发用排除法逐步缩小范围每步可以排除一行或一列虽然时间复杂度同样是 O(mn)但逻辑更贴合数据规律。所以遇到二维题先问清楚矩阵的组织方式再决定采用哪种二分策略。看到“有序矩阵”四个字就套全局二分是最容易踩的结构性大坑。4.3 二分答案把最优化问题变成判定问题这类题型近年来很常见比如“把数组分成 k 段每个段的和有一个上限问这个上限最小可能是多少”。直接求很难但如果反过来“给定一个上限 mid判断能不能在 k 段内完成”就变得非常简单。这种“对答案本身二分用判定函数决定缩上界还是缩下界”的思路就是二分答案。我写过的一个模板结构bool canPart(const vectorint 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 vectorint 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 vectorint 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初始 left0, right2, mid1, nums[1]3 4走第一分支left1left1, right2, mid1仍 nums[1]3 4left1完全不变于是死循环。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默认用你手写版本也最好保持一致。二分查找看似简单却是面试、竞赛和工程代码里出错率极高的算法。它的核心从来不是背代码而是把区间定义、循环不变量和取整方向这三样东西在动手前想清楚。希望这篇文章能帮你少踩几个坑尤其是那种“看起来没问题一跑却死循环”的诡异场景。 
长河君 · 2026/10/10 7:17:31 · 阅读 1.2k C++二分查找边界详解：区间模型、变体推导与死循环排查
先说一个我自己的经历。某次维护老模块时上游同学递过来一段不到二十行的二分查找代码逻辑看着很顺但测试一跑就卡住了——不是找不到值而是目标值不存在时返回的位置比预期偏右一格。我们花了一整个下午盯那几行代码最后发现只是mid更新时少了一个加一。二分查找就是这样一种算法。代码越短越容易在细节上翻车而且翻车的方式往往不是“找不到”而是“找出来的位置不对”。这篇文章我打算围绕 C 里二分查找的真正难点来写区间怎么定义边界怎么更新变体怎么推导以及在旋转数组、矩阵、二分答案这些场景里它到底怎么变形。适合刚学完基本语法、准备刷题或写工程代码的人也适合多年没碰二分、想一次性把边界想明白的老手。1. 二分查找的本质不是在搜值而是在排除区间很多人学二分查找记住的第一句话是“数组必须有序”。这个说法不算错但它掩盖了一个更本质的东西二分查找每一步做的事情不是“比较两个数相不相等”而是通过一次比较把当前搜索区间砍掉一半并保证目标值仍然留在剩下那一半里。想清楚这一点再回头看你写的每一行代码就会顺很多left和right不是两个普通变量它们共同描述了一个“目标值可能存在”的区间。每次循环都要确保这个区间没有被错误地缩小否则后面的一切都是白搭。1.1 什么场景才配用二分第一个判断标准是单调性。所谓单调不只是数组里的数字从小到大排还包括更广义的“判定结果单调”。比如“给定一个阈值x判断方案是否可行”如果x越大越容易满足那这个判定函数就是单调的就能在x的取值范围上做二分。第二个判断标准是“一次比较能排除一半”。在某一步你必须有办法知道目标不在某个半边。数组有序只是满足这个条件的最常见形式。例如旋转数组不是完全有序但它分成两段每段内部有序所以仍然可以用二分只是需要额外判断目标落在哪一段。但要注意并不是“沾了有序边”就一定能二分。比如一个数组里全是重复元素要求返回第一个等于目标值的位置这时候等值判断本身不可靠你得把比较条件从改成用 lower_bound 的思想来处理。这说明场景定了比较关系才能定顺序不能反过来。1.2 两个区间模型为什么 C 程序员必须分清写 C 二分第一行代码之前先回答一个问题你维护的区间是“左闭右闭”还是“左闭右开”先看最常见的左闭右闭写法int binarySearch(const 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; }再看左闭右开写法int binarySearchOpen(const vectorint 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 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; }为什么条件写的是nums[mid] target而不是nums[mid] target因为我们的不变量是“答案下标落在 [left, right] 中”。如果nums[mid] target说明mid下标一定不满足“大于等于 target”所以答案范围为[mid1, 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 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; } } 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 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; }注意这里right的初始值是nums.size()而不是nums.size()-1。因为“第一个不小于 target 的值”有可能落在数组末尾之外比如 target 比所有元素都大这时答案就是nums.size()。你把搜索区间的上界设成开区间才把这个情况包含进去。这也是为什么我一直强调“先选区间模型再写代码”。在这个函数里左闭右开是最自然的选择如果你的目标是“左闭右闭”那返回逻辑和初始值又要换一套很容易出问题。3.2 upper_bound 与最后一次出现的位置std::upper_bound返回“第一个大于给定值的迭代器”。手写版本只需要把判定条件反过来int upperBound(const 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 的位置先求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 可能是答案也可能答案在右侧所以保留 midleft mid。这时你发现mid left (right - left) / 2会导致相邻区间死循环所以要改成取右中位数int lastEqual(const vectorint 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 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; 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 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 val matrix[mid / n][mid % n]; if (val target) return true; if (val target) left mid 1; else right mid - 1; } return false; }但如果矩阵只是“每行递增每列递增”并无行间的大小承接关系就不能直接展平。我曾在一个题里用“先定位行再在行内二分”的思路结果因为没考虑列方向漏掉了跨行分布的情况。这种矩阵更适合从右上角或左下角出发用排除法逐步缩小范围每步可以排除一行或一列虽然时间复杂度同样是 O(mn)但逻辑更贴合数据规律。所以遇到二维题先问清楚矩阵的组织方式再决定采用哪种二分策略。看到“有序矩阵”四个字就套全局二分是最容易踩的结构性大坑。4.3 二分答案把最优化问题变成判定问题这类题型近年来很常见比如“把数组分成 k 段每个段的和有一个上限问这个上限最小可能是多少”。直接求很难但如果反过来“给定一个上限 mid判断能不能在 k 段内完成”就变得非常简单。这种“对答案本身二分用判定函数决定缩上界还是缩下界”的思路就是二分答案。我写过的一个模板结构bool canPart(const vectorint 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 vectorint 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 vectorint 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初始 left0, right2, mid1, nums[1]3 4走第一分支left1left1, right2, mid1仍 nums[1]3 4left1完全不变于是死循环。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默认用你手写版本也最好保持一致。二分查找看似简单却是面试、竞赛和工程代码里出错率极高的算法。它的核心从来不是背代码而是把区间定义、循环不变量和取整方向这三样东西在动手前想清楚。希望这篇文章能帮你少踩几个坑尤其是那种“看起来没问题一跑却死循环”的诡异场景。