刷 LeetCode 最让我无语的一件事就是碰到“二分查找”四个字。你觉得自己会吧——不就是两个指针夹中间吗真上了笔试或者周赛死循环、数组越界、答案差一位各种问题轮着来。我前前后后刷了几十道二分题从力扣 704 这种基础题到 875 爱吃香蕉的狒狒这种值域二分再到周赛里的综合难题踩过的坑足够写一篇文章了。这篇就把二分查找在力扣里怎么考、怎么写、怎么排错一次性说清楚。很多人的痛点是模板背得滚瓜烂熟一到新题就不会套或者写完以后自己测几个用例没问题一提交就“解答错误”。其实这些都是因为只记住了代码没理解二分到底在干什么。这篇文章不写虚的直接讲我实际刷题的思路、代码模板、易错点以及 LeetCode 上值得反复练的题目和对应解法希望能帮你把二分查找这块彻底拿捏住。1. 二分查找到底在考什么先想清楚再动手1.1 一个模板就能覆盖90%的题我在没想通之前背过三四个版本的二分模板什么左闭右闭、左闭右开、memcmp 变种结果一换题就乱。后来我意识到只要死死咬住一种写法把它的边界语义搞清楚90% 的题都能用一个模板改出来。我最推荐的是“左闭右闭”写法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; }这里最关键的认知是left和right都指向“当前还在搜索范围内”的下标所以left right表示这个范围还没空。一旦left right说明整个搜索范围内都找不到目标循环结束。这个模板里left或者right的每一次移动都必须跳过mid因为nums[mid]已经被比较过了不需要再纳入下一轮循环。这一个模子能直接套在力扣 704二分查找上改一下条件就能处理 35搜索插入位置、69x 的平方根这类变体。1.2 不是所有有序数组都适合无脑二分有一个误解我必须先纠正看到“有序”就二分这是新手最常见的错误。二分的适用场景是“基于某种规则可以不断排除一半的搜索空间”单调有序只是其中一种最典型的规则。比如力扣 33搜索旋转排序数组数组本身不整体有序但你把数组从中间切一刀总有一半是有序的我们只要判断目标值在哪半个区间里就能不断收缩范围。这种“部分有序”也可以用二分核心是找“可以排除掉哪一半”的判断条件。反过来如果一个数组完全随机没有任何可排除规则二分就完全失效。所以拿到题先别急着写循环先问自己一句我能不能在某一步直接确定答案不可能在左半边或者右半边能才继续往下写。1.3 下标二分和值域二分两套思维模型很多 LeetCode 中等题其实考的是“值域二分”而新手只会“下标二分”这是刷题认知上的一个分水岭。下标二分就是常规的在数组的下标范围[0, n-1]里找某个位置。力扣 704、35、34 都属于这一类。值域二分则是在“答案可能的取值范围”里二分逐个尝试答案然后验证这个答案是否可行。典型代表就是 875 爱吃香蕉的狒狒吃香蕉的速度k的取值范围是[1, max(piles)]题目要求在这个范围里二分找到最小的能够按时吃完的k。这类题必须写一个check(k)判定函数判断“以速度 k 吃能不能在 h 小时内吃完”然后根据判定结果收缩速度区间。区分这两种模型非常重要。我之前刷到 875 时一直尝试用下标二分去套怎么都想不明白“数组下标”对应什么。后来才明白二分查找的本质不是“数组有序”而是“单调性”在这个例子里速度越大吃完所需时间越小存在单调关系。你可以理解为二分查的是“单调函数上满足条件的点”数组只是这个函数的一种特殊存储形式。2. 背模板容易踩的三个坑死循环、越界、答案差一2.1 while 条件到底选 还是 由区间语义决定很多人纠结while (left right)还是while (left right)其实只要抓住一点你定义的区间是“左闭右闭”还是“左闭右开”。左闭右闭right nums.size() - 1搜索范围包含right所以left越过right时才停止用。左闭右开right nums.size()搜索范围不包含rightleft right时区间已经为空用。我自己习惯主用左闭右闭因为判断条件直觉上更顺left right时区间里还有一个数必须再查一次。用的时候退出循环后left的位置表示“第一个大于 target 的位置”这个特性在做“搜索插入位置”时非常好用。如果你混用不熟练建议选定一个套牢别今天写左闭右闭明天写左闭右开思维会打架。2.2 mid 计算别让 left right 先溢出这是一个非常经典的坑。int mid (left right) / 2在left和right都很大时加和可能超出 int 范围。力扣的测试数据一般不会故意卡这个但很多题目在极端数据下真的会溢出错。正确写法是int mid left (right - left) / 2;这行代码等价于(left right) / 2但不会先算left right。我面试时曾经手滑写成第一种面试官看了一眼就皱了眉头。这是一个非常好的“区分有经验和没经验”的细节。另外当left right是奇数时这个表达式得到的是靠左的中间值也就是向下取整。这个细节在处理死循环问题时非常关键下面会专门讲。2.3 left 和 right 怎么更新才不会漏答案更新边界时最容易出问题的场景是“只剩两个数”的时候。假设left 3right 4mid 3 (4-3)/2 3。如果你在某个分支里写的是left mid此时left仍然等于 3循环无法推进就死循环了。所以左闭右闭模板里有一个安全铁律更新边界时至少要排除掉 mid。比较完nums[mid]和 target 之后等于的情况已经 return小于的情况说明 target 在右半边让left mid 1大于的情况说明 target 在左半边让right mid - 1。只要遵循“mid 已经被检查过必须剔除”这个原则就不会出现死循环。如果你在写“寻找左侧边界”这种变体时想要left mid这种写法那要配合mid left (right - left 1) / 2这种向上取整不然就踩坑。我建议新手先不要玩这种高阶写法老老实实用排除法。2.4 左边界与右边界lower_bound 和 upper_bound 的写法转换力扣 34在排序数组中查找元素的第一个和最后一个位置要求找左右边界这是最容易混的题。我的做法是分别写两个二分语义非常明确int leftBound(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 1; else right mid - 1; // nums[mid] target继续往左找 } return left; // 此时 left 指向第一个 target 的位置 } int rightBound(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 1; // 继续往右找 else right mid - 1; } return right; // 此时 right 指向最后一个 target 的位置 }注意这两个函数返回的语义leftBound返回的是“第一个大于等于 target 的下标”rightBound返回的是“最后一个小于等于 target 的下标”。判断是否存在 target 时要检查返回下标是否越界以及nums[idx]是否等于 target。写多了你会发现其实各种二分变体都是在这两个边界函数上做小改动。3. 力扣二分题怎么刷从入门到进阶的真实题单3.1 入门三连704、35、69想打好二分基础先按顺序刷这三道别贪多。704 就是裸的二分查找直接把前面的模板默写一遍重点体会while循环退出条件和左右边界如何收缩。35 是搜索插入位置题面要求“如果 target 不存在返回它将会被按顺序插入的位置”。用左闭右闭模板时循环退出后left正好就是插入位置。为什么因为循环退出条件是left right此时nums[right] target或right -1而nums[left] target或left n所以left就是要插入的下标。这题能帮你真正理解“退出循环后 left 和 right 的位置有什么含义”。69 是求int sqrt(int x)经典的值域二分。答案范围是[0, x]我们要找满足mid * mid x的最大mid。注意两点一是用mid x / mid而不是mid * mid x避免乘法溢出二是这题也可以用牛顿迭代法但用二分不是为了炫技而是练习“把问题抽象成值域上找边界”的思维。我刷完这三题之后再看到类似“猜数字”“求最大最小值”的题心里才有底。3.2 边界与旋转数组34、153、33这三道题是二分进阶的第一道坎因为它们都不再是“直接找 target”这么简单而是考察你对区间单调性的理解。34 要求找左右边界上面已经给了模板。我建议先自己把两个函数各写一遍然后再合并成一次遍历的版本。合并版本比较绕初学不推荐两个独立二分反而更稳。153寻找旋转排序数组中的最小值不再给你 target而是让你在一个旋转过的有序数组里找最小值。我当时的思路是如果nums[mid] nums[right]说明最小值在右半边否则在左半边。为什么因为原数组有序旋转之后右半部分的末端nums[right]总是小于左半部分的某些元素只要 mid 落在旋转点左侧nums[mid]就会比nums[right]大。这个题本质上还是在利用“部分有序”来排除区间。33搜索旋转排序数组是 153 的进阶需要先判断哪一半有序再决定 target 可能在哪一半。做题时有个细节我踩过一次判断“左半边有序”时条件应该是nums[left] nums[mid]注意这个等号不能丢。为什么当区间只有两个元素时比如[1, 3]left 0, mid 0此时nums[left] nums[mid]如果去掉等号就会误判成“左半边无序”导致结果错误。这种边界光靠背套路根本发现不了只能靠手推小数据。3.3 值域二分实战875 爱吃香蕉的狒狒与 1011、410875 是我心里最典型的“值域二分”入门题网上也有人叫它“爱吃香蕉的狒狒”热词里有“073 爱吃香蕉的狒狒”其实就是这一题。题目给定piles数组和警卫回来的时间h求最小的吃香蕉速度k。核心思路分两步第一步确定二分范围。速度最小是 1最大是一堆香蕉的最大值因为超过最大值速度再快也没意义。第二步写判定函数模拟以速度k吃完所有香蕉需要的小时数。每堆香蕉需要的时间是(pile k - 1) / k也就是向上取整。代码如下class Solution { public: int minEatingSpeed(vectorint piles, int h) { int left 1, right *max_element(piles.begin(), piles.end()); auto can [](int speed) { long long hours 0; for (int p : piles) { hours (p speed - 1) / speed; } return hours h; }; while (left right) { int mid left (right - left) / 2; if (can(mid)) right mid; else left mid 1; } return left; } };注意这里我用了while (left right)和right mid的写法因为在值域二分的场景下我们要找的是“满足条件的最小值”这个模板比左闭右闭更直观。can(mid)为真说明速度够快可以再慢一点所以收缩右边界为假说明不够快必须提速所以收缩左边界。刷完 875 后建议接着刷 1011在 D 天内送达包裹的能力和 410分割数组的最大值。这两题本质上都是“给定一个上界/下界判断是否可行”判定函数的写法略有不同但二分的骨架一模一样。我把它们叫做“二分答案 贪心判定”组合这类题在力扣上数量不少是突破中等题的关键。3.4 中文 OJ 和竞赛场景里的二分从 PTA 到力扣周赛LeetCode 之外很多学校的实验课和 OJ 上也有二分题比如热词里的“sdut-c语言实验-二分查找”、“二分查找 pta 函数”。这类题表面上可能只让你补全一个函数比如 C 语言实验要求写一个BinarySearch(int a[], int n, int key)但考察点和力扣 704 没有任何区别。我当年在学校训练时踩过一个坑C 语言数组传参会退化成指针在函数里要用sizeof或计算数组长度会很别扭所以题目往往会直接传数组长度n。如果你是在 PTA 上做题记得保证函数签名和题目要求一致别多传参数、别改返回类型判题系统对函数接口非常严格。至于 LeetCode 周赛二分出现在竞赛题里时通常不会是孤立的而是作为“二分答案 贪心/前缀和/图论”的一个组合环节。比如热词里提到的周赛 430这类周赛题你打开题解会发现真正的难点往往在于能不能想到“答案具有单调性可以用二分枚举”而不是二分本身怎么写。我的建议是先在普通题库里把 875、1011、410 这类题刷熟再去周赛题里感受二分的“工具属性”。4. 现场排错实录面对死循环和答案差一怎么救回来4.1 不变式自查法把循环变量的含义写下来如果你写完二分一运行就死循环或者答案总是差一第一件事不是 printf 到处输出而是冷静下来把每个变量的“语义”写出来。我自己的做法是写注释// 循环开始前 // [left, right] 范围内包含所有可能的目标位置 // nums[mid] 是当前要检查的元素 // 每次更新后新的区间依然满足这个含义只要能保证这个“区间包含所有可能答案”的不变式成立逻辑上就不会漏答案。死循环的本质是更新之后区间没有变小也就是left mid或right mid且区间长度本来就是 1。对照不变式检查一遍通常立刻能发现问题。我发生过一次印象很深的排错当时写“寻找左边界的二分”把if (nums[mid] target)写成了if (nums[mid] target)导致等于 target 时右边界没有收缩结果在有多重复元素时永远停在最右边的那个位置上。这种错误光靠单步调试很难看出来但把不变式写清楚一眼就能定位。4.2 手推三类测试用例二分题自己测的时候别只盯着普通用例要刻意构造三类边界用例目标在数组最左边或最右边比如nums [1, 3, 5]分别查1和5。目标不存在且位于数组中间比如查4这时候需要确认返回的正确位置或 -1。数组只有一个元素比如[7]查7和查6都要测。数组为空如果题目允许比如[]这时候要确保不会访问nums[0]。我每次测完这些用例心里的底气会立刻上一个台阶。很多“提交一次过”的二分代码其实只是普通用例过了边界用例根本没跑过。4.3 写一个对拍器用暴力算法验证对于 875、1011 这种“二分答案”类题目最稳的验证方式是自己写一个暴力循环从 1 到最大值逐个试看哪个答案最小。然后写一个随机数据生成器把二分结果和暴力结果对比。这个思路在 ACM 刷题里叫“对拍”在力扣上写本地验证同样好用。举个例子875 题的暴力验证代码非常简单int brute(vectorint piles, int h) { int maxVal *max_element(piles.begin(), piles.end()); for (int k 1; k maxVal; k) { long long hours 0; for (int p : piles) hours (p k - 1) / k; if (hours h) return k; } return -1; }然后随机生成几十组小规模数据把minEatingSpeed和brute的结果逐一比对。这一类验证我建议每个“二分答案”题都做一遍既能发现自己思路哪里不对也能加深对判定函数的理解。以前我觉得写对拍器很浪费时间直到有一次用它抓出了一个隐藏 bug才意识到它有多值。5. 刷题之外的实话二分查找怎么才算真正会了5.1 二分真正难的不是写循环而是看出“单调性”也许你已经发现了二分查找的模板非常固定哪怕手生翻一下笔记也能写对。真正的分水岭是你能不能在一道题里识别出可以二分查找的那个单调关系。比如 410 题“分割数组的最大值”你要在“数组和的上界”上二分判定“是否能将数组分成不超过 m 段且每段和都不超过该上界”。第一次见到这个题的人几乎很难把“最大值最小化”和“二分查找”联系起来。但一旦你建立起“最大值最小化或最小值最大化优先考虑二分答案”的直觉这类题就变得套路化。单调性是二分的前提写判定函数才是主体。所以刷二分题的时候我的核心训练目标不是默写 while 循环而是训练自己读题之后快速抽象出自变量和因变量然后确认“自变量增大时因变量是否朝着同一个方向变化”。5.2 我的个人习惯用区间收缩替代记忆模板网上有很多二分模板什么“左闭右开”“纯 while (l r)”“查找左侧边界右侧边界”。我后来找到一个最适合自己的习惯统一用左闭右闭的区间循环条件统一用while (left right)更新规则统一是“排除 mid”。遇到要找最小满足条件的值这类题时我再切换到while (left right) right mid的写法。两种写法我会区分使用场景而不是混用。选模板的原则很简单哪种写法你能准确说出“退出循环那一刻left 和 right 分别指向什么位置”就用哪种。说不出的模板一律不背。面试时面试官更看重的往往是你能否清楚解释每一步的边界而不是背出一个看起来很高级的模板。5.3 复盘建议怎么判断自己真的会了我的自我检验方式很简单过一段时间后重新做一遍力扣 704、35、34、875 四道题要求自己不看任何笔记每道题在 10 分钟之内写完并一次提交通过。如果连 704 都出现边界错误说明基础还是虚的需要回到第 2 部分重新理解区间语义如果 34 能一次写对说明你对左右边界的掌握基本到位如果 875 能顺利写出判定函数并保证数据不溢出说明你已经理解了值域二分的骨架。这套自测方法我每隔两三个月会跑一遍。别看题简单很多刷了几百题的人突然让他裸写一个查找左边界的二分照样会卡壳几分钟。二分这个知识点很特殊代码可以很短想清楚却需要很长时间。你现在花在思考边界语义上的时间都会在后面的力扣刷题和周赛里赚回来。