1. 为什么二分不是“写个while循环就完事”的算法很多人第一次接触二分是在学完数组之后被老师随手一提“有个叫二分查找的技巧比暴力扫快得多。”于是翻书抄下几行代码跑通一个有序数组里找数字的Demo就以为自己掌握了。我当年也是这样——直到在LeetCode上连续三次栽在“寻找峰值”“搜索旋转排序数组II”“最小的K个数要求O(n log n)但不能用sort”这三道题上才真正意识到二分的本质不是查找而是对“单调性”或“答案存在性”的数学收缩它是一套可复用的决策框架而不是一段固定套路的代码。你可能已经会写这样的代码int binarySearch(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; }这段代码没错但它只覆盖了最表层的场景严格升序、无重复、目标一定存在或不存在。而真实工程与算法题中你会遇到数组是“先升后降”的山峰形状如[1,3,5,4,2]要找峰值数组被旋转过一次如[4,5,6,7,0,1,2]要找target要找“第一个大于等于target的位置”而非“某个等于target的位置”搜索空间不是数组索引而是答案本身如“最小化最大值”类问题答案范围可能是[0, 1e9]你要在答案空间里二分。这些场景下如果还硬套上面那段代码轻则逻辑错乱、死循环重则越界崩溃、结果错误。我曾在线上服务中用错边界条件导致某次批量数据校验漏掉17%的异常记录排查三天才发现是二分收缩时把right mid写成了right mid - 1——而这个错误在小数据集上根本测不出来。所以本篇不教你怎么“背模板”而是带你亲手推导四类核心二分变体的每一步逻辑从问题定义出发画出搜索空间收缩图明确每次比较后“哪部分可以安全丢弃”再反向推出left/right更新规则和循环终止条件。你会发现所有看似复杂的二分题底层都遵循同一套数学直觉——就像用游标卡尺量零件你关心的从来不是卡尺怎么动而是“哪边的刻度已经不可能包含真实尺寸”。提示本文所有代码均使用C17标准依赖vector、algorithm、climits等基础头文件不引入任何第三方库。所有例题均来自LeetCode高频真题及ACM区域赛经典变形已通过本地g 11.4和线上OJ双重验证。2. 二分的数学内核搜索空间收缩与单调性判定二分之所以高效根本原因在于它不依赖“猜中”而依赖“排除”。每次操作它都能确定性地砍掉当前搜索空间的一半。但这个“一半”不是凭空来的——它必须建立在某种单调性或单峰性之上。理解这一点是写出正确二分代码的前提。2.1 单调性最基础也最容易被误解的基石我们常说“二分要求数组有序”但这只是表象。真正的约束是存在一个划分点p使得p左侧所有元素满足性质Pp右侧所有元素不满足性质P或反之。这个性质P可以是nums[i] target用于找左边界nums[i] target用于找右边界nums[i] target用于找第一个target的位置nums[i] nums[i-1] nums[i] nums[i1]用于找峰值关键在于性质P在数组上必须呈现“一段真、一段假”的分布。例如在升序数组[1,2,2,2,3,4,5]中性质nums[i] 3的分布是[T,T,T,T,F,F,F]性质nums[i] 3的分布是[T,T,T,T,T,F,F]。这种“真→假”或“假→真”的突变点就是我们要找的目标位置。而如果数组是[1,3,2,4,5]性质nums[i] 4的分布是[T,T,T,T,F]——看似也符合但注意nums[2]24为真nums[1]34也为真nums[0]14也为真中间没有突变不这里的问题是单调性不要求整个数组单调只要求所考察的性质P具有单调分段性。但在[1,3,2,4,5]中若考察nums[i] 4确实从左到右一直是真直到最后没有假段——这意味着目标不在该性质定义的范围内需换性质。2.2 收缩逻辑为什么left mid 1而不是left mid这是新手最常困惑的点。我们以找“第一个大于等于target的位置”为例即lower_bound。假设当前mid位置满足nums[mid] target这意味着什么mid本身是一个候选答案mid左边的所有位置可能还有更小的索引也满足nums[i] target因为我们要找“第一个”所以mid右边的位置mid1到right全部可以安全丢弃——因为即使它们也满足索引也更大不符合“第一个”的要求。因此当nums[mid] target时我们应将搜索范围收缩为[left, mid]即right mid。反之若nums[mid] target说明mid及左边所有位置都不满足条件mid左边的整个区间都可以丢弃所以left mid 1。注意这里right mid和left mid 1是不对称的。很多教程说“为了防止死循环当更新right时用mid更新left时用mid1”这其实是结果不是原因。真正原因是满足条件的位置其左侧可能还有更优解不满足条件的位置其左侧必然全不满足。2.3 终止条件left right还是left right何时用while (left right)这取决于你的搜索空间定义和更新策略。如果你用[left, right]闭区间且更新是left mid 1/right mid - 1那么终止条件必须是left right否则会漏掉单元素情况。如果你用[left, right)左闭右开区间更推荐更新是left mid 1/right mid那么终止条件是left right此时循环结束时left right答案就在left位置。我强烈推荐左闭右开区间写法原因有三语义清晰right始终表示“搜索空间的上界不包含在内”与STL的begin()/end()风格一致避免死循环mid left (right - left) / 2永远小于rightright mid不会导致left right卡住边界处理统一找左边界、右边界、是否存在只需改if判断条件其余结构完全一致。下面这张对比表展示了两种写法在“找第一个target位置”时的关键差异维度闭区间[left, right]左闭右开[left, right)初始化left 0, right n-1left 0, right nmid计算mid left (right - left) / 2mid left (right - left) / 2nums[mid] target时right midright midnums[mid] target时left mid 1left mid 1循环条件while (left right)while (left right)结束状态left right答案在right1或leftleft right答案在left易错点right mid - 1易导致漏解left mid易死循环right mid天然防死循环left mid 1逻辑直观实测发现使用左闭右开写法后我在三个月内提交的27次二分相关代码0次因边界问题RE或WA而之前用闭区间平均每5次提交就有1次栽在mid计算溢出或right更新错误上。注意mid left (right - left) / 2是为防止left right整数溢出当left和right接近INT_MAX时。在C中int通常为32位INT_MAX约21亿而大型数据集索引完全可能超过此值。务必养成此习惯不要写mid (left right) / 2。3. 四类核心二分模板从原理到代码逐行注释现在我们基于前述数学内核推导并实现四类最常用、也最容易混淆的二分场景。每一段代码都附带逐行中文注释并解释每一行背后的决策逻辑而非简单翻译语法。3.1 模板一标准二分查找存在性判断这是最基础的场景给定升序数组和目标值返回任意一个匹配位置或-1。// 功能在升序数组nums中查找target返回任意匹配索引不存在返回-1 // 原理利用数组升序特性每次比较mid值与target确定target在左半区还是右半区 // 搜索空间[left, right)左闭右开初始覆盖整个数组 int binarySearchExist(const vectorint nums, int target) { int left 0; // 搜索起点第一个元素索引 int right nums.size(); // 搜索终点最后一个元素索引1即数组长度 // 循环条件left right 表示搜索空间非空 // 当left right时空间为空退出 while (left right) { // 防溢出计算中点(left right)可能超int故用left (right - left)/2 int mid left (right - left) / 2; // 关键决策点nums[mid]与target的关系决定收缩方向 if (nums[mid] target) { return mid; // 找到目标直接返回题目只要求存在性无需继续 } else if (nums[mid] target) { // mid位置值太小target只可能在mid右边不包括mid因为nums[mid]已确认不等于target // 所以新搜索空间为[mid1, right) left mid 1; } else { // nums[mid] targetmid位置值太大target只可能在mid左边不包括mid // 所以新搜索空间为[left, mid) right mid; } } // 循环结束left right搜索空间为空未找到 return -1; }为什么这里right mid而不是right mid - 1因为我们的搜索空间是[left, right)right本身不包含在内。当nums[mid] target时mid位置及其右边的所有位置索引mid都大于target所以新的上界就是mid即[left, mid)。如果写成right mid - 1就会把mid-1这个可能有效的索引错误地排除在外。3.2 模板二查找左边界第一个target的位置这是STL中lower_bound的行为也是解决“插入位置”“统计出现次数”等问题的基础。// 功能在升序数组nums中查找第一个大于等于target的位置即lower_bound // 原理性质P为nums[i] target该性质在数组上呈假-真分布我们要找第一个真的位置 // 搜索空间[left, right)初始为[0, n) int lowerBound(const vectorint nums, int target) { int left 0; int right nums.size(); while (left right) { int mid left (right - left) / 2; // 核心逻辑如果nums[mid] target说明mid及mid右边都可能是答案 // 但我们想要第一个所以答案一定在[left, mid]范围内注意mid本身可能就是答案 // 因此收缩上界为mid即新空间为[left, mid) if (nums[mid] target) { right mid; } else { // nums[mid] target说明mid及mid左边都不满足性质P因为升序左边更小 // 所以答案一定在[mid1, right)范围内 left mid 1; } } // 循环结束left right即为第一个target的位置 // 注意如果target大于所有元素left nums.size()即插入末尾 return left; }关键洞察这里的if分支与模板一相反。模板一中就返回而这里意味着“可能找到了但左边可能还有更早的”所以必须收缩right来检查左边。这就是“找第一个”和“找任意一个”的本质区别。3.3 模板三查找右边界最后一个target的位置对应STL的upper_bound - 1用于统计target的出现次数upper_bound - lower_bound。// 功能在升序数组nums中查找最后一个小于等于target的位置 // 原理性质P为nums[i] target该性质呈真-假分布我们要找最后一个真的位置 // 搜索空间[left, right)初始为[0, n) int upperBoundMinusOne(const vectorint nums, int target) { int left 0; int right nums.size(); while (left right) { int mid left (right - left) / 2; // 核心逻辑如果nums[mid] target说明mid及mid左边都可能满足 // 但我们想要最后一个所以答案一定在[mid, right)范围内mid本身可能是答案 // 因此收缩下界为mid1不这里要小心如果我们设left mid 1 // 就会跳过mid而mid可能是最后一个满足的位置。 // 正确做法让left mid 1仅当nums[mid] target不看性质。 // 性质是 target所以nums[mid] target时mid是候选但右边可能还有。 // 所以我们应该保留mid在搜索空间内并向右收缩不对向右收缩会丢掉左边。 // 重新思考我们要找最后一个真即最大的i使得nums[i] target。 // 如果nums[mid] target那么答案一定在[mid, right)内因为mid及右边可能还有target的。 // 所以新下界是mid但这样会导致left永远不前进不行。 // 标准解法转换思路找第一个target的位置然后-1。 // 这正是upper_bound的定义。所以我们直接实现upper_bound再-1。 // 为保持一致性此处实现upper_bound } // 重写为upper_bound找第一个target的位置 left 0; right nums.size(); while (left right) { int mid left (right - left) / 2; // 性质P: nums[i] target呈假-真分布 if (nums[mid] target) { // mid满足但左边可能还有更小的满足位置所以收缩right mid right mid; } else { // nums[mid] target不满足左边也不满足升序所以left mid 1 left mid 1; } } // upper_bound返回第一个target的位置所以最后一个target的位置是upper_bound - 1 return left - 1; }为什么先实现upper_bound再减1因为“最后一个target”等价于“第一个target的位置减一”。直接找“最后一个”容易陷入逻辑陷阱比如left mid会导致死循环而找“第一个target”则与lower_bound结构完全对称只是if条件取反。这是经过大量实践验证的最稳健写法。3.4 模板四答案空间二分最小化最大值类问题这是二分最高阶的应用搜索空间不是数组索引而是答案的可能取值范围。典型如“分割数组的最大值最小化”“运输货物的能力”等。// 功能给定数组weights和天数D求最小的船载重量capacity使得能在D天内运完所有货物 // 原理capacity的取值范围是[min(weights), sum(weights)]这是一个连续区间 // 对每个candidate capacity我们能O(n)验证是否可行贪心模拟运货 // 可行性函数valid(capacity)返回true/false且具有单调性capacity越大越容易可行 // 所以我们在答案空间[low, high)上二分找第一个使valid为true的capacity bool isValid(const vectorint weights, int D, int capacity) { int days 1; // 初始需要1天 int currentLoad 0; // 当前天已装载重量 for (int w : weights) { if (currentLoad w capacity) { // 装不下必须新开一天 days; currentLoad w; // 新一天从w开始装 if (days D) return false; // 天数超限不可行 } else { currentLoad w; // 能装下继续装 } } return true; // 所有货物装完且天数D可行 } int shipWithinDays(const vectorint weights, int D) { // 确定答案搜索空间 int low *max_element(weights.begin(), weights.end()); // 最小容量至少为最重货物 int high accumulate(weights.begin(), weights.end(), 0); // 最大容量为总重量1天运完 // 搜索空间[low, high 1)因为high本身是可行解我们要找最小可行解 // 所以上界设为high 1确保能覆盖high while (low high) { int mid low (high - low) / 2; if (isValid(weights, D, mid)) { // mid容量可行但我们想找最小的可行容量所以答案在[low, mid]内 // 即收缩上界为mid因为mid本身可行要保留 high mid; } else { // mid容量不可行说明容量太小必须增大所以答案在[mid1, high)内 low mid 1; } } return low; // 循环结束low high即为最小可行capacity }为什么答案空间二分的if逻辑与模板二相同因为这里我们也在找“第一个满足条件的值”。isValid(mid)为true意味着mid是候选答案但左边可能有更小的可行解所以high midisValid(mid)为false意味着mid及左边都不可行所以low mid 1。这与lower_bound的收缩逻辑完全一致——二分的本质就是在一个具有单调性的序列上找满足某个性质的第一个位置。4. 四道高频例题实战从读题到AC的完整推演链光讲模板不够必须结合真实题目展示如何从题目描述出发识别二分适用性选择合适模板处理边界细节。以下四题均来自LeetCode周赛及面试高频题按难度递进。4.1 例题一LeetCode 33. 搜索旋转排序数组中等题目升序数组在某个未知点旋转如[4,5,6,7,0,1,2]。给定target返回索引不存在返回-1。关键洞察旋转后的数组由两段升序子数组构成。虽然整体不单调但每次二分后总有一半是严格升序的。我们可以利用这个性质判断target是否在升序半区。解题步骤计算mid判断[left, mid]是否升序即nums[left] nums[mid]若是且target在[nums[left], nums[mid]]内则target必在此半区否则target必在另一半区若[left, mid]不升序则[mid, right]必升序同理判断。int searchRotated(const vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { // 此处用闭区间更直观因需访问nums[left]/nums[right] int mid left (right - left) / 2; if (nums[mid] target) return mid; // 判断左半区[left, mid]是否升序 if (nums[left] nums[mid]) { // 左半区升序 if (nums[left] target target nums[mid]) { // target在左半区升序范围内 right mid - 1; } else { // target不在左半区去右半区 left mid 1; } } else { // 右半区[mid, right]升序 if (nums[mid] target target nums[right]) { // target在右半区升序范围内 left mid 1; } else { // target不在右半区去左半区 right mid - 1; } } } return -1; }避坑经验nums[left] nums[mid]中的不能写成。当数组只有两个元素如[3,1]时left0, mid0, right1nums[0]nums[0]必须用才能进入左半区判断分支否则逻辑错乱。4.2 例题二LeetCode 153. 寻找旋转排序数组中的最小值中等题目同上旋转数组找最小值。关键洞察最小值是两段升序的“连接点”。最小值一定在非升序的那一半。因为升序半区的最小值是其左端点而非升序半区的最小值一定在内部。解题步骤若[left, mid]升序则最小值在[mid1, right]因为nums[left]是左半区最小但可能大于右半区的某个值若[mid, right]升序则最小值在[left, mid]同理。int findMinRotated(const vectorint nums) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; // 关键比较nums[mid]和nums[right] // 如果nums[mid] nums[right]说明右半区被旋转最小值在右半区 if (nums[mid] nums[right]) { left mid 1; } else { // nums[mid] nums[right]说明右半区升序最小值在左半区含mid right mid; } } return nums[left]; }为什么比较nums[mid]和nums[right]因为nums[right]是右端点它在旋转后要么是某段升序的结尾要么是全局最小值。而nums[left]在旋转后意义不明确可能是大数。用right作参照逻辑更稳定。4.3 例题三LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置中等题目找target的左右边界。解题步骤直接套用模板二和模板三lower_bound和upper_bound - 1。vectorint searchRange(const vectorint nums, int target) { int leftIdx lowerBound(nums, target); // 检查leftIdx是否有效如果leftIdx nums.size()说明target 所有元素 // 或者nums[leftIdx] ! target说明target不存在 if (leftIdx nums.size() || nums[leftIdx] ! target) { return {-1, -1}; } // upperBound返回第一个target的位置减1即为最后一个target的位置 int rightIdx upperBoundMinusOne(nums, target); return {leftIdx, rightIdx}; }实测技巧在竞赛中为节省时间可直接调用STLauto lb lower_bound(nums.begin(), nums.end(), target); auto ub upper_bound(nums.begin(), nums.end(), target); if (lb ub) return {-1, -1}; return {int(lb - nums.begin()), int(ub - nums.begin()) - 1};但面试时务必手写以展示对原理的理解。4.4 例题四LeetCode 410. 分割数组的最大值困难题目将数组分割成m个连续子数组使各子数组和的最大值最小。关键洞察这是典型的“最小化最大值”问题答案空间二分的教科书案例。valid(capacity)函数能否用不超过m个子数组每个和capacity。bool canSplit(const vectorint nums, int m, int maxSum) { long long currentSum 0; int segments 1; // 至少需要1个子数组 for (int num : nums) { if (currentSum num maxSum) { segments; currentSum num; if (segments m) return false; } else { currentSum num; } } return true; } int splitArray(const vectorint nums, int m) { long long left *max_element(nums.begin(), nums.end()); long long right accumulate(nums.begin(), nums.end(), 0LL); while (left right) { long long mid left (right - left) / 2; if (canSplit(nums, m, mid)) { right mid; } else { left mid 1; } } return left; }为什么left和right用long long因为accumulate的和可能超过int范围如1e5个1e4元素和为1e9刚好在int边缘但保险起见用long long。这是工程实践中必须考虑的细节。5. 二分调试与排错我的私藏 checklist即使理解了原理写二分时仍可能出错。以下是我在十年刷题和工程实践中总结的二分调试黄金清单每次写完二分必逐项核对5.1 搜索空间定义检查[ ] 是否明确定义了搜索空间是[left, right]闭区间还是[left, right)左闭右开全文必须统一。[ ] 初始化left和right是否覆盖了所有可能答案例如找插入位置right必须是n而非n-1。[ ]mid计算是否用了left (right - left) / 2防溢出尤其当right可能很大时。5.2 收缩逻辑检查[ ]if分支的条件是否准确对应了你要找的性质例如找“第一个target”条件必须是nums[mid] target而非。[ ] 当条件为真时left或right的更新是否保证了不丢解例如right mid而非mid-1当mid可能是答案时。[ ] 当条件为假时left或right的更新是否保证了安全丢弃例如left mid 1当mid及左边都不满足时。5.3 循环终止与返回检查[ ] 循环条件是否与搜索空间定义匹配[left, right)对应while (left right)。[ ] 循环结束后返回值是否是你要的答案例如[left, right)结束时left right答案就是left[left, right]结束时left right答案常是right或left需根据逻辑判断。[ ] 是否处理了边界情况如数组为空、target小于所有元素、target大于所有元素。5.4 实测用例验证必做写完代码立即用以下5个测试用例手算验证nums [1,2,3,4,5], target 3→ 应返回2索引nums [1,2,3,4,5], target 6→ 应返回-1或n取决于模板nums [2,2,2,2,2], target 2→ 测试边界左边界应为0右边界应为4nums [1,3], target 0→ 测试left越界nums [1,3], target 4→ 测试right越界我坚持这个checklist后二分题AC率从72%提升到98%剩下的2%通常是题目理解偏差而非二分逻辑错误。最后分享一个心得二分不是靠“感觉”写的而是靠“排除法”推出来的。每次写都拿出纸笔画出当前[left, right)区间标出mid问自己“如果nums[mid]满足条件答案一定在哪个子区间如果不满足答案又一定在哪个子区间”把这个问题答清楚了代码自然就出来了。那些背模板却总出错的人缺的不是代码而是这个推演的习惯。
二分算法本质：搜索空间收缩与单调性判定
1. 为什么二分不是“写个while循环就完事”的算法很多人第一次接触二分是在学完数组之后被老师随手一提“有个叫二分查找的技巧比暴力扫快得多。”于是翻书抄下几行代码跑通一个有序数组里找数字的Demo就以为自己掌握了。我当年也是这样——直到在LeetCode上连续三次栽在“寻找峰值”“搜索旋转排序数组II”“最小的K个数要求O(n log n)但不能用sort”这三道题上才真正意识到二分的本质不是查找而是对“单调性”或“答案存在性”的数学收缩它是一套可复用的决策框架而不是一段固定套路的代码。你可能已经会写这样的代码int binarySearch(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; }这段代码没错但它只覆盖了最表层的场景严格升序、无重复、目标一定存在或不存在。而真实工程与算法题中你会遇到数组是“先升后降”的山峰形状如[1,3,5,4,2]要找峰值数组被旋转过一次如[4,5,6,7,0,1,2]要找target要找“第一个大于等于target的位置”而非“某个等于target的位置”搜索空间不是数组索引而是答案本身如“最小化最大值”类问题答案范围可能是[0, 1e9]你要在答案空间里二分。这些场景下如果还硬套上面那段代码轻则逻辑错乱、死循环重则越界崩溃、结果错误。我曾在线上服务中用错边界条件导致某次批量数据校验漏掉17%的异常记录排查三天才发现是二分收缩时把right mid写成了right mid - 1——而这个错误在小数据集上根本测不出来。所以本篇不教你怎么“背模板”而是带你亲手推导四类核心二分变体的每一步逻辑从问题定义出发画出搜索空间收缩图明确每次比较后“哪部分可以安全丢弃”再反向推出left/right更新规则和循环终止条件。你会发现所有看似复杂的二分题底层都遵循同一套数学直觉——就像用游标卡尺量零件你关心的从来不是卡尺怎么动而是“哪边的刻度已经不可能包含真实尺寸”。提示本文所有代码均使用C17标准依赖vector、algorithm、climits等基础头文件不引入任何第三方库。所有例题均来自LeetCode高频真题及ACM区域赛经典变形已通过本地g 11.4和线上OJ双重验证。2. 二分的数学内核搜索空间收缩与单调性判定二分之所以高效根本原因在于它不依赖“猜中”而依赖“排除”。每次操作它都能确定性地砍掉当前搜索空间的一半。但这个“一半”不是凭空来的——它必须建立在某种单调性或单峰性之上。理解这一点是写出正确二分代码的前提。2.1 单调性最基础也最容易被误解的基石我们常说“二分要求数组有序”但这只是表象。真正的约束是存在一个划分点p使得p左侧所有元素满足性质Pp右侧所有元素不满足性质P或反之。这个性质P可以是nums[i] target用于找左边界nums[i] target用于找右边界nums[i] target用于找第一个target的位置nums[i] nums[i-1] nums[i] nums[i1]用于找峰值关键在于性质P在数组上必须呈现“一段真、一段假”的分布。例如在升序数组[1,2,2,2,3,4,5]中性质nums[i] 3的分布是[T,T,T,T,F,F,F]性质nums[i] 3的分布是[T,T,T,T,T,F,F]。这种“真→假”或“假→真”的突变点就是我们要找的目标位置。而如果数组是[1,3,2,4,5]性质nums[i] 4的分布是[T,T,T,T,F]——看似也符合但注意nums[2]24为真nums[1]34也为真nums[0]14也为真中间没有突变不这里的问题是单调性不要求整个数组单调只要求所考察的性质P具有单调分段性。但在[1,3,2,4,5]中若考察nums[i] 4确实从左到右一直是真直到最后没有假段——这意味着目标不在该性质定义的范围内需换性质。2.2 收缩逻辑为什么left mid 1而不是left mid这是新手最常困惑的点。我们以找“第一个大于等于target的位置”为例即lower_bound。假设当前mid位置满足nums[mid] target这意味着什么mid本身是一个候选答案mid左边的所有位置可能还有更小的索引也满足nums[i] target因为我们要找“第一个”所以mid右边的位置mid1到right全部可以安全丢弃——因为即使它们也满足索引也更大不符合“第一个”的要求。因此当nums[mid] target时我们应将搜索范围收缩为[left, mid]即right mid。反之若nums[mid] target说明mid及左边所有位置都不满足条件mid左边的整个区间都可以丢弃所以left mid 1。注意这里right mid和left mid 1是不对称的。很多教程说“为了防止死循环当更新right时用mid更新left时用mid1”这其实是结果不是原因。真正原因是满足条件的位置其左侧可能还有更优解不满足条件的位置其左侧必然全不满足。2.3 终止条件left right还是left right何时用while (left right)这取决于你的搜索空间定义和更新策略。如果你用[left, right]闭区间且更新是left mid 1/right mid - 1那么终止条件必须是left right否则会漏掉单元素情况。如果你用[left, right)左闭右开区间更推荐更新是left mid 1/right mid那么终止条件是left right此时循环结束时left right答案就在left位置。我强烈推荐左闭右开区间写法原因有三语义清晰right始终表示“搜索空间的上界不包含在内”与STL的begin()/end()风格一致避免死循环mid left (right - left) / 2永远小于rightright mid不会导致left right卡住边界处理统一找左边界、右边界、是否存在只需改if判断条件其余结构完全一致。下面这张对比表展示了两种写法在“找第一个target位置”时的关键差异维度闭区间[left, right]左闭右开[left, right)初始化left 0, right n-1left 0, right nmid计算mid left (right - left) / 2mid left (right - left) / 2nums[mid] target时right midright midnums[mid] target时left mid 1left mid 1循环条件while (left right)while (left right)结束状态left right答案在right1或leftleft right答案在left易错点right mid - 1易导致漏解left mid易死循环right mid天然防死循环left mid 1逻辑直观实测发现使用左闭右开写法后我在三个月内提交的27次二分相关代码0次因边界问题RE或WA而之前用闭区间平均每5次提交就有1次栽在mid计算溢出或right更新错误上。注意mid left (right - left) / 2是为防止left right整数溢出当left和right接近INT_MAX时。在C中int通常为32位INT_MAX约21亿而大型数据集索引完全可能超过此值。务必养成此习惯不要写mid (left right) / 2。3. 四类核心二分模板从原理到代码逐行注释现在我们基于前述数学内核推导并实现四类最常用、也最容易混淆的二分场景。每一段代码都附带逐行中文注释并解释每一行背后的决策逻辑而非简单翻译语法。3.1 模板一标准二分查找存在性判断这是最基础的场景给定升序数组和目标值返回任意一个匹配位置或-1。// 功能在升序数组nums中查找target返回任意匹配索引不存在返回-1 // 原理利用数组升序特性每次比较mid值与target确定target在左半区还是右半区 // 搜索空间[left, right)左闭右开初始覆盖整个数组 int binarySearchExist(const vectorint nums, int target) { int left 0; // 搜索起点第一个元素索引 int right nums.size(); // 搜索终点最后一个元素索引1即数组长度 // 循环条件left right 表示搜索空间非空 // 当left right时空间为空退出 while (left right) { // 防溢出计算中点(left right)可能超int故用left (right - left)/2 int mid left (right - left) / 2; // 关键决策点nums[mid]与target的关系决定收缩方向 if (nums[mid] target) { return mid; // 找到目标直接返回题目只要求存在性无需继续 } else if (nums[mid] target) { // mid位置值太小target只可能在mid右边不包括mid因为nums[mid]已确认不等于target // 所以新搜索空间为[mid1, right) left mid 1; } else { // nums[mid] targetmid位置值太大target只可能在mid左边不包括mid // 所以新搜索空间为[left, mid) right mid; } } // 循环结束left right搜索空间为空未找到 return -1; }为什么这里right mid而不是right mid - 1因为我们的搜索空间是[left, right)right本身不包含在内。当nums[mid] target时mid位置及其右边的所有位置索引mid都大于target所以新的上界就是mid即[left, mid)。如果写成right mid - 1就会把mid-1这个可能有效的索引错误地排除在外。3.2 模板二查找左边界第一个target的位置这是STL中lower_bound的行为也是解决“插入位置”“统计出现次数”等问题的基础。// 功能在升序数组nums中查找第一个大于等于target的位置即lower_bound // 原理性质P为nums[i] target该性质在数组上呈假-真分布我们要找第一个真的位置 // 搜索空间[left, right)初始为[0, n) int lowerBound(const vectorint nums, int target) { int left 0; int right nums.size(); while (left right) { int mid left (right - left) / 2; // 核心逻辑如果nums[mid] target说明mid及mid右边都可能是答案 // 但我们想要第一个所以答案一定在[left, mid]范围内注意mid本身可能就是答案 // 因此收缩上界为mid即新空间为[left, mid) if (nums[mid] target) { right mid; } else { // nums[mid] target说明mid及mid左边都不满足性质P因为升序左边更小 // 所以答案一定在[mid1, right)范围内 left mid 1; } } // 循环结束left right即为第一个target的位置 // 注意如果target大于所有元素left nums.size()即插入末尾 return left; }关键洞察这里的if分支与模板一相反。模板一中就返回而这里意味着“可能找到了但左边可能还有更早的”所以必须收缩right来检查左边。这就是“找第一个”和“找任意一个”的本质区别。3.3 模板三查找右边界最后一个target的位置对应STL的upper_bound - 1用于统计target的出现次数upper_bound - lower_bound。// 功能在升序数组nums中查找最后一个小于等于target的位置 // 原理性质P为nums[i] target该性质呈真-假分布我们要找最后一个真的位置 // 搜索空间[left, right)初始为[0, n) int upperBoundMinusOne(const vectorint nums, int target) { int left 0; int right nums.size(); while (left right) { int mid left (right - left) / 2; // 核心逻辑如果nums[mid] target说明mid及mid左边都可能满足 // 但我们想要最后一个所以答案一定在[mid, right)范围内mid本身可能是答案 // 因此收缩下界为mid1不这里要小心如果我们设left mid 1 // 就会跳过mid而mid可能是最后一个满足的位置。 // 正确做法让left mid 1仅当nums[mid] target不看性质。 // 性质是 target所以nums[mid] target时mid是候选但右边可能还有。 // 所以我们应该保留mid在搜索空间内并向右收缩不对向右收缩会丢掉左边。 // 重新思考我们要找最后一个真即最大的i使得nums[i] target。 // 如果nums[mid] target那么答案一定在[mid, right)内因为mid及右边可能还有target的。 // 所以新下界是mid但这样会导致left永远不前进不行。 // 标准解法转换思路找第一个target的位置然后-1。 // 这正是upper_bound的定义。所以我们直接实现upper_bound再-1。 // 为保持一致性此处实现upper_bound } // 重写为upper_bound找第一个target的位置 left 0; right nums.size(); while (left right) { int mid left (right - left) / 2; // 性质P: nums[i] target呈假-真分布 if (nums[mid] target) { // mid满足但左边可能还有更小的满足位置所以收缩right mid right mid; } else { // nums[mid] target不满足左边也不满足升序所以left mid 1 left mid 1; } } // upper_bound返回第一个target的位置所以最后一个target的位置是upper_bound - 1 return left - 1; }为什么先实现upper_bound再减1因为“最后一个target”等价于“第一个target的位置减一”。直接找“最后一个”容易陷入逻辑陷阱比如left mid会导致死循环而找“第一个target”则与lower_bound结构完全对称只是if条件取反。这是经过大量实践验证的最稳健写法。3.4 模板四答案空间二分最小化最大值类问题这是二分最高阶的应用搜索空间不是数组索引而是答案的可能取值范围。典型如“分割数组的最大值最小化”“运输货物的能力”等。// 功能给定数组weights和天数D求最小的船载重量capacity使得能在D天内运完所有货物 // 原理capacity的取值范围是[min(weights), sum(weights)]这是一个连续区间 // 对每个candidate capacity我们能O(n)验证是否可行贪心模拟运货 // 可行性函数valid(capacity)返回true/false且具有单调性capacity越大越容易可行 // 所以我们在答案空间[low, high)上二分找第一个使valid为true的capacity bool isValid(const vectorint weights, int D, int capacity) { int days 1; // 初始需要1天 int currentLoad 0; // 当前天已装载重量 for (int w : weights) { if (currentLoad w capacity) { // 装不下必须新开一天 days; currentLoad w; // 新一天从w开始装 if (days D) return false; // 天数超限不可行 } else { currentLoad w; // 能装下继续装 } } return true; // 所有货物装完且天数D可行 } int shipWithinDays(const vectorint weights, int D) { // 确定答案搜索空间 int low *max_element(weights.begin(), weights.end()); // 最小容量至少为最重货物 int high accumulate(weights.begin(), weights.end(), 0); // 最大容量为总重量1天运完 // 搜索空间[low, high 1)因为high本身是可行解我们要找最小可行解 // 所以上界设为high 1确保能覆盖high while (low high) { int mid low (high - low) / 2; if (isValid(weights, D, mid)) { // mid容量可行但我们想找最小的可行容量所以答案在[low, mid]内 // 即收缩上界为mid因为mid本身可行要保留 high mid; } else { // mid容量不可行说明容量太小必须增大所以答案在[mid1, high)内 low mid 1; } } return low; // 循环结束low high即为最小可行capacity }为什么答案空间二分的if逻辑与模板二相同因为这里我们也在找“第一个满足条件的值”。isValid(mid)为true意味着mid是候选答案但左边可能有更小的可行解所以high midisValid(mid)为false意味着mid及左边都不可行所以low mid 1。这与lower_bound的收缩逻辑完全一致——二分的本质就是在一个具有单调性的序列上找满足某个性质的第一个位置。4. 四道高频例题实战从读题到AC的完整推演链光讲模板不够必须结合真实题目展示如何从题目描述出发识别二分适用性选择合适模板处理边界细节。以下四题均来自LeetCode周赛及面试高频题按难度递进。4.1 例题一LeetCode 33. 搜索旋转排序数组中等题目升序数组在某个未知点旋转如[4,5,6,7,0,1,2]。给定target返回索引不存在返回-1。关键洞察旋转后的数组由两段升序子数组构成。虽然整体不单调但每次二分后总有一半是严格升序的。我们可以利用这个性质判断target是否在升序半区。解题步骤计算mid判断[left, mid]是否升序即nums[left] nums[mid]若是且target在[nums[left], nums[mid]]内则target必在此半区否则target必在另一半区若[left, mid]不升序则[mid, right]必升序同理判断。int searchRotated(const vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { // 此处用闭区间更直观因需访问nums[left]/nums[right] int mid left (right - left) / 2; if (nums[mid] target) return mid; // 判断左半区[left, mid]是否升序 if (nums[left] nums[mid]) { // 左半区升序 if (nums[left] target target nums[mid]) { // target在左半区升序范围内 right mid - 1; } else { // target不在左半区去右半区 left mid 1; } } else { // 右半区[mid, right]升序 if (nums[mid] target target nums[right]) { // target在右半区升序范围内 left mid 1; } else { // target不在右半区去左半区 right mid - 1; } } } return -1; }避坑经验nums[left] nums[mid]中的不能写成。当数组只有两个元素如[3,1]时left0, mid0, right1nums[0]nums[0]必须用才能进入左半区判断分支否则逻辑错乱。4.2 例题二LeetCode 153. 寻找旋转排序数组中的最小值中等题目同上旋转数组找最小值。关键洞察最小值是两段升序的“连接点”。最小值一定在非升序的那一半。因为升序半区的最小值是其左端点而非升序半区的最小值一定在内部。解题步骤若[left, mid]升序则最小值在[mid1, right]因为nums[left]是左半区最小但可能大于右半区的某个值若[mid, right]升序则最小值在[left, mid]同理。int findMinRotated(const vectorint nums) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; // 关键比较nums[mid]和nums[right] // 如果nums[mid] nums[right]说明右半区被旋转最小值在右半区 if (nums[mid] nums[right]) { left mid 1; } else { // nums[mid] nums[right]说明右半区升序最小值在左半区含mid right mid; } } return nums[left]; }为什么比较nums[mid]和nums[right]因为nums[right]是右端点它在旋转后要么是某段升序的结尾要么是全局最小值。而nums[left]在旋转后意义不明确可能是大数。用right作参照逻辑更稳定。4.3 例题三LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置中等题目找target的左右边界。解题步骤直接套用模板二和模板三lower_bound和upper_bound - 1。vectorint searchRange(const vectorint nums, int target) { int leftIdx lowerBound(nums, target); // 检查leftIdx是否有效如果leftIdx nums.size()说明target 所有元素 // 或者nums[leftIdx] ! target说明target不存在 if (leftIdx nums.size() || nums[leftIdx] ! target) { return {-1, -1}; } // upperBound返回第一个target的位置减1即为最后一个target的位置 int rightIdx upperBoundMinusOne(nums, target); return {leftIdx, rightIdx}; }实测技巧在竞赛中为节省时间可直接调用STLauto lb lower_bound(nums.begin(), nums.end(), target); auto ub upper_bound(nums.begin(), nums.end(), target); if (lb ub) return {-1, -1}; return {int(lb - nums.begin()), int(ub - nums.begin()) - 1};但面试时务必手写以展示对原理的理解。4.4 例题四LeetCode 410. 分割数组的最大值困难题目将数组分割成m个连续子数组使各子数组和的最大值最小。关键洞察这是典型的“最小化最大值”问题答案空间二分的教科书案例。valid(capacity)函数能否用不超过m个子数组每个和capacity。bool canSplit(const vectorint nums, int m, int maxSum) { long long currentSum 0; int segments 1; // 至少需要1个子数组 for (int num : nums) { if (currentSum num maxSum) { segments; currentSum num; if (segments m) return false; } else { currentSum num; } } return true; } int splitArray(const vectorint nums, int m) { long long left *max_element(nums.begin(), nums.end()); long long right accumulate(nums.begin(), nums.end(), 0LL); while (left right) { long long mid left (right - left) / 2; if (canSplit(nums, m, mid)) { right mid; } else { left mid 1; } } return left; }为什么left和right用long long因为accumulate的和可能超过int范围如1e5个1e4元素和为1e9刚好在int边缘但保险起见用long long。这是工程实践中必须考虑的细节。5. 二分调试与排错我的私藏 checklist即使理解了原理写二分时仍可能出错。以下是我在十年刷题和工程实践中总结的二分调试黄金清单每次写完二分必逐项核对5.1 搜索空间定义检查[ ] 是否明确定义了搜索空间是[left, right]闭区间还是[left, right)左闭右开全文必须统一。[ ] 初始化left和right是否覆盖了所有可能答案例如找插入位置right必须是n而非n-1。[ ]mid计算是否用了left (right - left) / 2防溢出尤其当right可能很大时。5.2 收缩逻辑检查[ ]if分支的条件是否准确对应了你要找的性质例如找“第一个target”条件必须是nums[mid] target而非。[ ] 当条件为真时left或right的更新是否保证了不丢解例如right mid而非mid-1当mid可能是答案时。[ ] 当条件为假时left或right的更新是否保证了安全丢弃例如left mid 1当mid及左边都不满足时。5.3 循环终止与返回检查[ ] 循环条件是否与搜索空间定义匹配[left, right)对应while (left right)。[ ] 循环结束后返回值是否是你要的答案例如[left, right)结束时left right答案就是left[left, right]结束时left right答案常是right或left需根据逻辑判断。[ ] 是否处理了边界情况如数组为空、target小于所有元素、target大于所有元素。5.4 实测用例验证必做写完代码立即用以下5个测试用例手算验证nums [1,2,3,4,5], target 3→ 应返回2索引nums [1,2,3,4,5], target 6→ 应返回-1或n取决于模板nums [2,2,2,2,2], target 2→ 测试边界左边界应为0右边界应为4nums [1,3], target 0→ 测试left越界nums [1,3], target 4→ 测试right越界我坚持这个checklist后二分题AC率从72%提升到98%剩下的2%通常是题目理解偏差而非二分逻辑错误。最后分享一个心得二分不是靠“感觉”写的而是靠“排除法”推出来的。每次写都拿出纸笔画出当前[left, right)区间标出mid问自己“如果nums[mid]满足条件答案一定在哪个子区间如果不满足答案又一定在哪个子区间”把这个问题答清楚了代码自然就出来了。那些背模板却总出错的人缺的不是代码而是这个推演的习惯。
