尧图网站开发 
好久没正儿八经写一篇刷题类的总结分享了。这两年带团队面试总爱拿一道二分查找的变种题当试金石结果很出乎意料能一次性写对边界条件的人比能写出红黑树的还少。这个现象本身就很说明问题——二分查找作为力扣LeetCode上最基础、最经典的算法之一表面看只有几行代码可一旦涉及边界处理、循环不变量、单调性判断就特别容易翻车。所以专门整理一篇针对二分查找的力扣题解思路与实践总结从模板原理到热题拆解、从死循环排查到刷题路线一次性把这块内容讲透。不管你是刚开始刷力扣的初学者还是准备面试想查漏补缺的进阶选手这篇内容都值得你花二十分钟仔细过一遍。很多人觉得二分查找简单不就是“左指针、右指针、中间值比较”三件套吗真到写代码的时候就发现要么是left right和left right搞混要么是mid更新时忘了1/-1导致死循环再要么是题目稍微包装一下比如旋转数组、二维矩阵、答案单调性判断就完全不知道怎么下手。说白了二分查找难的不是“模板”而是“什么时候能用二分”和“边界到底怎么定”这两件事。这篇博客就围绕这两个核心痛点展开把力扣上高频的二分题按类型拆解逐题分析思路、代码、易错点最后再整理一套适合新手到进阶的刷题路线。1. 二分查找的本质与力扣考题的内在逻辑1.1 为什么二分查找是面试和力扣的常青树先说个基本事实二分查找不是“在有序数组里找某个数”这么简单。力扣上关于二分的题目多达上百道从最基础的704. 二分查找到33. 搜索旋转排序数组、4. 寻找两个正序数组的中位数、875. 爱吃香蕉的狒狒这类看似和“查找”毫无关系的题核心都用到了同一套思想——通过不断缩小“可行解”的范围把线性复杂度降到对数复杂度。这就引出一个关键点二分查找的适用条件不是“数组有序”而是问题具有单调性。什么意思呢就是存在一个判定函数check(mid)当mid满足某个条件时答案一定在左半边或右半边于是可以放心地砍掉一半搜索空间。有序数组满足这个性质旋转数组的“二段性”也满足甚至“吃香蕉的最少速度”这种优化问题因为速度越快越有可能在时限内吃完也天然具备单调性。理解到这一层你才算真正入门了二分。我在力扣刷题攻略里反复给读者强调一句话凡是求“最小可行值”或“最大可行值”的题目先想想答案区间是否具备单调性如果有大概率可以用二分答案来做。这比死记硬背十几道题有用得多。1.2 力扣热题100中二分的分布与特点翻开力扣 hot100热题100二分查找相关的题目几乎都是经典中的经典。比如35. 搜索插入位置、74. 搜索二维矩阵、33. 搜索旋转排序数组、34. 在排序数组中查找元素的第一个和最后一个位置、153. 寻找旋转排序数组中的最小值、4. 寻找两个正序数组的中位数。如果你正在跟着热题100刷题看到这些题目不要跳它们是一套完整的二分训练序列。这些题目的设计逻辑是递进的先是老老实实的有序数组基础题训练你对模板的肌肉记忆然后是带旋转的、带重复值的变形题训练你分析“二段性”的能力再往后是二维矩阵、双数组训练你把问题抽象成“区间划分”的能力最后是像875. 爱吃香蕉的狒狒这种二分答案题训练你把优化问题转化成判定问题的能力。一环扣一环刷完这一组你对二分的理解会上一个台阶。热词里还出现了leetcode 1273这道题本身不是纯二分题但它相关的树结构处理和二分思想结合可以加深“分类讨论单调搜索”的理解思路后面的路线部分我再细说。2. 二分查找核心模板拆解左闭右闭与左闭右开2.1 所有二分模板都源于同一个循环不变量很多初学者学二分最大的问题就是今天背一套写法明天看题解又换一套最后越背越乱。实际上力扣上的二分题解不管怎么变都离不开两个边界约定左闭右闭[left, right]和左闭右开[left, right)。你要做的不是两套都背而是挑一套自己顺手的然后所有的题都用这一套保持循环不变量不变。我自己的习惯是左闭右闭也就是区间的左端点和右端点都包含在搜索范围内。对应的代码框架是def binary_search(nums, target): left, right 0, len(nums) - 1 # 注意 right 是最后一个有效下标 while left right: # 当区间不为空时继续 mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 # target 在右半边左边界收缩 else: right mid - 1 # target 在左半边右边界收缩 return -1请特别注意三个细节。第一while条件是而不是因为你的搜索区间是[left, right]当left right时区间里还有一个元素不能提前退出。第二mid的写法用left (right - left) // 2不要用(left right) // 2这样可以避免两个大整数相加时溢出虽然 Python 里整数不溢出但要养成好习惯其他语言里这就是经典 bug。第三更新边界时left mid 1、right mid - 1保证每次循环区间都在缩小不会因为mid仍落在区间内而死循环。2.2 实战对比left right 与 left right 的差异我在实际刷题和帮别人 review 代码时见过最多的错误就是把写成。比如704. 二分查找数组[-1, 0, 3, 5, 9, 12]目标值9。如果你用left right当left和right都指向下标 4 的时候循环就退出了你根本没检查下标 4 的元素导致返回-1。有些同学可能会说“我看别人的题解里也有用left right的写法而且也能过。”没错那是因为他们用的是左闭右开写法或者配合right mid而不是mid - 1来保证不会漏查元素。这里我需要强调一下并不是某个写法绝对对而是你必须清楚自己用的是哪种区间定义然后所有细节都跟区间定义保持一致。为了方便对比我把左闭右开模板也贴出来def binary_search(nums, target): left, right 0, len(nums) # 右边界是开区间所以初始化为 len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid return -1在这个写法里right是不包含在搜索区间内的所以初始化是len(nums)而不是len(nums)-1nums[mid] target时让right mid而不是mid - 1因为mid本身已经被查过了但right是开区间直接设成mid就表示“下一轮不再考虑mid及其右边”。这个逻辑也是自洽的。我的个人建议是平时练习就用左闭右闭因为它的终止条件left right和人工思考“区间空了吗”最吻合但遇到求“第一个大于等于 target 的位置”这类 lower_bound 问题左闭右开往往更顺手因为right mid天然保留了“可能位置”的信息。两种模板都要会但先吃透一种。3. 力扣高频二分题逐题拆解与代码实现3.1 基础查找类704 与 35这两道题是二分的敲门砖。704. 二分查找就是裸的模板题直接套上面的代码即可不需要额外分析。重点说下35. 搜索插入位置。题目要求给定排序数组和一个目标值如果找到目标值就返回下标找不到就返回它会被按顺序插入的位置。很多人一上来就想着“先查一下查不到再找插入位置”结果代码写得很丑陋。实际上这题要找的就是第一个大于等于 target 的元素下标也就是 C 里的lower_bound。用左闭右闭模板怎么改呢思路是正常二分如果找到 target 直接返回如果没找到循环退出时left指向的位置正好是第一个大于 target 的元素下标也就是插入位置。所以代码可以写成def searchInsert(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: left mid 1 else: right mid - 1 return left这里有个小细节值得琢磨nums[mid] target的时候我没有提前返回而是走了else分支把right收到mid - 1。这样最后返回的left就是最左侧的等于target的位置。所以这个代码不仅能处理“插入位置”顺带还能处理“第一个等于 target 的下标”这类问题。这就是为什么我一直强调理解边界比背代码重要——同一个模板稍微变一下能解决的问题就不一样了。3.2 旋转数组类33 与 15333. 搜索旋转排序数组是 hot100 里非常有代表性的一道题。数组本身就是有序的但在某个未知位置旋转了一次比如[0,1,2,4,5,6,7]变成[4,5,6,7,0,1,2]。直接对整个数组做普通二分肯定不行因为整体已经不满足单调递增了。但是仔细观察会发现无论mid落在哪里左半段或右半段至少有一段是严格有序的。我当年第一次做这道题时思路是判断nums[left] nums[mid]如果成立说明左半段[left, mid]是有序的接下来判断target是否落在这个有序区间内如果落进去就搜左边否则搜右边。右半段有序的情况对称处理。核心代码如下def search(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: return mid if nums[left] nums[mid]: # 左半段有序 if nums[left] target nums[mid]: right mid - 1 else: left mid 1 else: # 右半段有序 if nums[mid] target nums[right]: left mid 1 else: right mid - 1 return -1这个题的坑点在于边界条件是而不是。为什么因为当区间只有两个元素时比如[3, 1]left0, mid0此时nums[left] nums[mid]如果不加等号会误判“左半段有序”然后走向错误分支。加等号可以保证当nums[left] nums[mid]时也按照左半段有序处理反而能正确处理只有两个元素的情况。这个细节我是被测试用例教训过之后才彻底记住的。153. 寻找旋转排序数组中的最小值比搜索目标值更简单一点。它的核心思想是比较nums[mid]和nums[right]如果nums[mid] nums[right]说明最小值在右半段否则最小值在左半段或就是mid本身。因为要找最小值所以即使nums[mid] nums[right]也不能把right设成mid - 1而要设成mid否则可能会跳过最小值。这个逻辑刚好对应左闭右开写法的right mid模式用起来很自然。3.3 二维矩阵与双数组74 与 474. 搜索二维矩阵表面上是一个二维题实际上可以把它“拉直”成一维因为矩阵的每一行从左到右递增并且下一行的第一个元素大于上一行的最后一个元素所以整个矩阵按行拼接后就是一个有序数组。于是直接用一维二分即可只需要做一次坐标映射def searchMatrix(matrix, target): m, n len(matrix), len(matrix[0]) left, right 0, m * n - 1 while left right: mid left (right - left) // 2 mid_val matrix[mid // n][mid % n] if mid_val target: return True elif mid_val target: left mid 1 else: right mid - 1 return False这道题的难点不是二分而是“把一个有序的二维结构映射到一维坐标”。mid // n是行号mid % n是列号这个映射关系想明白了代码就是套模板。面试时如果能把这道题的思路讲清楚基本能给面试官留下“这人是真的理解二分而不是背题”的印象。4. 寻找两个正序数组的中位数是二分里比较难的一道也是 hot100 的常客。这题如果用合并数组再取中位数的方法时间复杂度是O(mn)但题目要求O(log(mn))于是只能用二分。核心思路是在两个数组中分别划分割线i和j使得左半部分元素总数等于右半部分或左半比右半多一个并且左半部分的最大值不超过右半部分的最小值。通过二分调整i的位置同时j根据i自动确定因为存在关系i j (mn1)//2。这道题的代码细节非常多包括奇偶长度处理、一个数组为空、以及越界访问的保护。我建议初学者先不要死磕4把它放到后期进阶。热词里提到的leetcode 1273和三维接雨水这类难题也都适合在基础二分彻底掌握之后再碰。3.4 二分答案类875 与 1011二分答案也叫“对答案二分”是力扣近两年特别喜欢考的题型875. 爱吃香蕉的狒狒就是最经典的入门题之一这题在热词里也出现了。题目给了一堆香蕉堆piles和一个时限h让你求“在 h 小时内吃完所有香蕉的最小速度k”。如果直接求最小速度你可能会想用贪心、模拟但一个一个试速度太慢。而这里的关键性质是速度k越大吃完所需时间越短满足“时间 h”这个条件的速度值在数轴上是单调的——速度太小不满足速度足够大一定满足。既然具备单调性就可以在速度范围[1, max(piles)]上做二分不断试探当前的mid速度是否能在时限内吃完。判断函数是核心需要单独写一个辅助函数def can_finish(piles, h, speed): total_hours sum((p speed - 1) // speed for p in piles) return total_hours h def minEatingSpeed(piles, h): left, right 1, max(piles) while left right: mid left (right - left) // 2 if can_finish(piles, h, mid): right mid # 速度快了或刚好尝试缩小 else: left mid 1 # 速度慢了必须加大 return left这里的取整方式要留意(p speed - 1) // speed是向上取整表示每一堆需要吃多少小时不能直接用p // speed否则会少算时间。另外这题用left right的模板更合适因为我们要找的是“可行域的左边界”right mid保留了候选答案不丢left mid 1排除掉不可行的值。同类型的题还有1011. 在 D 天内送达包裹的能力、410. 分割数组的最大值它们都是用二分答案把“求最小值”问题转化为“判断某个值是否可行”问题。一旦掌握这个套路你会突然发现很多看似毫无头绪的困难题都有了统一的解题抓手。4. 二分查找的变形套路与高频易错点排查4.1 lower_bound 与 upper_bound面试手撕重灾区力扣34. 在排序数组中查找元素的第一个和最后一个位置问的其实就是lower_bound和upper_bound。很多人在这个题上栽跟头是因为试图用一次二分同时找到左边界和右边界结果逻辑纠缠不清。我的建议是写两个辅助函数一个找第一个 target 的位置一个找第一个 target 的位置最后一个等于 target 的区间就是[lower_bound, upper_bound - 1]。用左闭右开模板写这两个函数会非常顺def lower_bound(nums, target): left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: left mid 1 else: right mid return left def upper_bound(nums, target): left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: left mid 1 else: right mid return left两个函数唯一的区别是lower_bound判定条件用 target移动左指针upper_bound用 target移动左指针。这种写法之所以不容易出错是因为right mid意味着mid仍然有可能是答案我们只是把右边界收缩到mid处继续探索不会丢失候选值。想通这一点你就再也不会为 left/right 到底要不要1而纠结了。4.2 死循环、越界与中点选择三大经典坑二分查找初学阶段最容易踩的坑有三个我一个个说。第一个是死循环。死循环的根源是left和right更新不合理导致某一个位置被无限重复检查。比如在左闭右闭模板里如果查到nums[mid] target后写left mid而不是left mid 1当left和right相邻时mid永远是left左指针永远不动程序就卡死了。解决办法很简单每轮循环必须使区间长度严格缩小所以排除mid时要1或-1。第二个是数组越界。这个在34和4这类题里特别常见。比如34题中如果所有元素都小于targetlower_bound返回len(nums)直接用它去访问nums[left]就会越界。所以查找前要做一次lower_bound len(nums) and nums[lower_bound] target的判断缺一不可。这个细节我见过太多人写漏。第三个是中点选择。mid left (right - left) // 2是向下取整// 2换成(right - left 1) // 2是向上取整。在普通二分里两种都行但在需要配合left mid或right mid的模板里选错方向会触发死循环。我的经验是如果代码里出现left midmid就必须向上取整如果出现right midmid就向下取整。这是一条很好用的口诀能帮你快速排查死循环问题。4.3 判定函数的单调性能不能用二分的关键最后再说一个很多教程没有强调的点写二分答案题之前先问自己一句判定函数check(mid)真的单调吗如果答案区间不是单调的二分就会给出错误结果。举个例子假设有个问题要你求某个值但这个值“太高也不行、太低也不行”在中间某段才可行那就不是单调函数而是分布函数不能用普通二分。通常需要把问题转换成“找最大的不满足”、“找最小的满足”这类带方向性的问题才可以用二分。热词里提到的三维接雨水、复杂树形结构题目如果要用二分都是因为问题本身可以剥出一层单调性来。判断单调性的实操方法是随手画一个草图横轴是mid候选答案纵轴是判定结果True/False。如果真值分布是False...False True...True那就可以用二分找分界点如果出现True False True这种多段分布就得想别的办法了。掌握这个分析习惯能少走很多弯路。5. 从 hot100 到周赛二分查找刷题路线与扩展方向5.1 力扣热题100的二分题目顺序推荐如果你现在打开力扣热题100想把二分的题刷一遍我建议按下面的顺序来不要跳704. 二分查找背熟模板理解左闭右闭和左闭右开的区别。35. 搜索插入位置练习 lower_bound 思想把模板改造成“返回第一个大于等于”的写法。34. 在排序数组中查找元素的第一个和最后一个位置练习同时写 lower_bound 和 upper_bound。74. 搜索二维矩阵练习一维坐标到二维矩阵的映射。33. 搜索旋转排序数组理解“二段性”学会在局部有序段中二分。153. 寻找旋转排序数组中的最小值进一步训练边界处理。875. 爱吃香蕉的狒狒正式进入二分答案的领域。4. 寻找两个正序数组的中位数进阶题学有余力再上。这个顺序不是随便排的它遵循“基础模板 - 边界变形 - 结构变形 - 思维模型变形”的递进。我发现很多读者直接刷33和4刷到怀疑人生其实就是因为前面的基础能力还没夯实。5.2 周赛与 hot100 之外如何用二分思想扩展解题视野热词里的leetcode周赛430和leetcode 1273让我想到一个常见问题很多人把二分题限制在“数组题”标签里遇到树、图、字符串就想不到二分。实际上二分的本质是“答案空间上的搜索”所以它可以出现在任何题型里。比如树上的某些“第 k 大”问题可以先二分答案再做一次树形 DP 或遍历来判断是否可行再比如热词里提到的 fpga 二分查找树编码器这是硬件设计里用二分树结构优化查找路径的思路和软件二分的决策过程异曲同工。我自己的习惯是每周参加一次力扣周赛不管能不能全做出来都刻意训练自己“看一道题先问单调性”。如果一道题能转化为“给定 x判断是否可行”我就倾向于用二分答案来解。这个习惯让我在遇到陌生题型时不至于完全没思路至少有一个通用的突破口。5.3 给你的刷题记录表与复盘方法最后分享一个我自己整理的二分题复盘表建议你在本地维护一份题号题型分类使用模板核心易错点是否掌握704基础查找左闭右闭终止条件是35lower_bound左闭右闭返回 left是34边界查找左闭右开越界判断否33旋转数组左闭右闭等号细节复盘153旋转数组左闭右开right mid复盘74二维映射左闭右闭坐标换算是875二分答案左闭右开向上取整否4进阶二分自定义奇偶处理否每次刷完一道题想一想“如果我把题目条件改一下还能不能用同样的方法”比如 704 改成“有重复元素”你就应该联想到 3433 改成“允许重复元素”你需要思考怎么跳过相同值避免left right失效。这种改编训练比盲目刷新题更能加深对二分的理解。我自己带过的不少读者一开始也是各种边界 bug 不断后来坚持“每道题必须写清楚循环不变量并解释为什么更新 left/right”一段时间后正确率高了很多。说白了二分查找不是靠天赋而是靠一套清晰的思维框架加刻意练习。最后再分享一个我踩过多次坑之后养成的习惯提交代码前先拿一个长度为 1 的数组、一个长度为 2 的数组、以及 target 在数组左边界/右边界/不存在这几种极端用例在脑子里跑一遍。二分题 90% 的错误都藏在这些极端情况里提前过一遍能省下不少提交失败的挫败感。希望你也能借助这套思路把力扣上的二分题稳稳拿下。 
好久没正儿八经写一篇刷题类的总结分享了。这两年带团队面试总爱拿一道二分查找的变种题当试金石结果很出乎意料能一次性写对边界条件的人比能写出红黑树的还少。这个现象本身就很说明问题——二分查找作为力扣LeetCode上最基础、最经典的算法之一表面看只有几行代码可一旦涉及边界处理、循环不变量、单调性判断就特别容易翻车。所以专门整理一篇针对二分查找的力扣题解思路与实践总结从模板原理到热题拆解、从死循环排查到刷题路线一次性把这块内容讲透。不管你是刚开始刷力扣的初学者还是准备面试想查漏补缺的进阶选手这篇内容都值得你花二十分钟仔细过一遍。很多人觉得二分查找简单不就是“左指针、右指针、中间值比较”三件套吗真到写代码的时候就发现要么是left right和left right搞混要么是mid更新时忘了1/-1导致死循环再要么是题目稍微包装一下比如旋转数组、二维矩阵、答案单调性判断就完全不知道怎么下手。说白了二分查找难的不是“模板”而是“什么时候能用二分”和“边界到底怎么定”这两件事。这篇博客就围绕这两个核心痛点展开把力扣上高频的二分题按类型拆解逐题分析思路、代码、易错点最后再整理一套适合新手到进阶的刷题路线。1. 二分查找的本质与力扣考题的内在逻辑1.1 为什么二分查找是面试和力扣的常青树先说个基本事实二分查找不是“在有序数组里找某个数”这么简单。力扣上关于二分的题目多达上百道从最基础的704. 二分查找到33. 搜索旋转排序数组、4. 寻找两个正序数组的中位数、875. 爱吃香蕉的狒狒这类看似和“查找”毫无关系的题核心都用到了同一套思想——通过不断缩小“可行解”的范围把线性复杂度降到对数复杂度。这就引出一个关键点二分查找的适用条件不是“数组有序”而是问题具有单调性。什么意思呢就是存在一个判定函数check(mid)当mid满足某个条件时答案一定在左半边或右半边于是可以放心地砍掉一半搜索空间。有序数组满足这个性质旋转数组的“二段性”也满足甚至“吃香蕉的最少速度”这种优化问题因为速度越快越有可能在时限内吃完也天然具备单调性。理解到这一层你才算真正入门了二分。我在力扣刷题攻略里反复给读者强调一句话凡是求“最小可行值”或“最大可行值”的题目先想想答案区间是否具备单调性如果有大概率可以用二分答案来做。这比死记硬背十几道题有用得多。1.2 力扣热题100中二分的分布与特点翻开力扣 hot100热题100二分查找相关的题目几乎都是经典中的经典。比如35. 搜索插入位置、74. 搜索二维矩阵、33. 搜索旋转排序数组、34. 在排序数组中查找元素的第一个和最后一个位置、153. 寻找旋转排序数组中的最小值、4. 寻找两个正序数组的中位数。如果你正在跟着热题100刷题看到这些题目不要跳它们是一套完整的二分训练序列。这些题目的设计逻辑是递进的先是老老实实的有序数组基础题训练你对模板的肌肉记忆然后是带旋转的、带重复值的变形题训练你分析“二段性”的能力再往后是二维矩阵、双数组训练你把问题抽象成“区间划分”的能力最后是像875. 爱吃香蕉的狒狒这种二分答案题训练你把优化问题转化成判定问题的能力。一环扣一环刷完这一组你对二分的理解会上一个台阶。热词里还出现了leetcode 1273这道题本身不是纯二分题但它相关的树结构处理和二分思想结合可以加深“分类讨论单调搜索”的理解思路后面的路线部分我再细说。2. 二分查找核心模板拆解左闭右闭与左闭右开2.1 所有二分模板都源于同一个循环不变量很多初学者学二分最大的问题就是今天背一套写法明天看题解又换一套最后越背越乱。实际上力扣上的二分题解不管怎么变都离不开两个边界约定左闭右闭[left, right]和左闭右开[left, right)。你要做的不是两套都背而是挑一套自己顺手的然后所有的题都用这一套保持循环不变量不变。我自己的习惯是左闭右闭也就是区间的左端点和右端点都包含在搜索范围内。对应的代码框架是def binary_search(nums, target): left, right 0, len(nums) - 1 # 注意 right 是最后一个有效下标 while left right: # 当区间不为空时继续 mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 # target 在右半边左边界收缩 else: right mid - 1 # target 在左半边右边界收缩 return -1请特别注意三个细节。第一while条件是而不是因为你的搜索区间是[left, right]当left right时区间里还有一个元素不能提前退出。第二mid的写法用left (right - left) // 2不要用(left right) // 2这样可以避免两个大整数相加时溢出虽然 Python 里整数不溢出但要养成好习惯其他语言里这就是经典 bug。第三更新边界时left mid 1、right mid - 1保证每次循环区间都在缩小不会因为mid仍落在区间内而死循环。2.2 实战对比left right 与 left right 的差异我在实际刷题和帮别人 review 代码时见过最多的错误就是把写成。比如704. 二分查找数组[-1, 0, 3, 5, 9, 12]目标值9。如果你用left right当left和right都指向下标 4 的时候循环就退出了你根本没检查下标 4 的元素导致返回-1。有些同学可能会说“我看别人的题解里也有用left right的写法而且也能过。”没错那是因为他们用的是左闭右开写法或者配合right mid而不是mid - 1来保证不会漏查元素。这里我需要强调一下并不是某个写法绝对对而是你必须清楚自己用的是哪种区间定义然后所有细节都跟区间定义保持一致。为了方便对比我把左闭右开模板也贴出来def binary_search(nums, target): left, right 0, len(nums) # 右边界是开区间所以初始化为 len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid return -1在这个写法里right是不包含在搜索区间内的所以初始化是len(nums)而不是len(nums)-1nums[mid] target时让right mid而不是mid - 1因为mid本身已经被查过了但right是开区间直接设成mid就表示“下一轮不再考虑mid及其右边”。这个逻辑也是自洽的。我的个人建议是平时练习就用左闭右闭因为它的终止条件left right和人工思考“区间空了吗”最吻合但遇到求“第一个大于等于 target 的位置”这类 lower_bound 问题左闭右开往往更顺手因为right mid天然保留了“可能位置”的信息。两种模板都要会但先吃透一种。3. 力扣高频二分题逐题拆解与代码实现3.1 基础查找类704 与 35这两道题是二分的敲门砖。704. 二分查找就是裸的模板题直接套上面的代码即可不需要额外分析。重点说下35. 搜索插入位置。题目要求给定排序数组和一个目标值如果找到目标值就返回下标找不到就返回它会被按顺序插入的位置。很多人一上来就想着“先查一下查不到再找插入位置”结果代码写得很丑陋。实际上这题要找的就是第一个大于等于 target 的元素下标也就是 C 里的lower_bound。用左闭右闭模板怎么改呢思路是正常二分如果找到 target 直接返回如果没找到循环退出时left指向的位置正好是第一个大于 target 的元素下标也就是插入位置。所以代码可以写成def searchInsert(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: left mid 1 else: right mid - 1 return left这里有个小细节值得琢磨nums[mid] target的时候我没有提前返回而是走了else分支把right收到mid - 1。这样最后返回的left就是最左侧的等于target的位置。所以这个代码不仅能处理“插入位置”顺带还能处理“第一个等于 target 的下标”这类问题。这就是为什么我一直强调理解边界比背代码重要——同一个模板稍微变一下能解决的问题就不一样了。3.2 旋转数组类33 与 15333. 搜索旋转排序数组是 hot100 里非常有代表性的一道题。数组本身就是有序的但在某个未知位置旋转了一次比如[0,1,2,4,5,6,7]变成[4,5,6,7,0,1,2]。直接对整个数组做普通二分肯定不行因为整体已经不满足单调递增了。但是仔细观察会发现无论mid落在哪里左半段或右半段至少有一段是严格有序的。我当年第一次做这道题时思路是判断nums[left] nums[mid]如果成立说明左半段[left, mid]是有序的接下来判断target是否落在这个有序区间内如果落进去就搜左边否则搜右边。右半段有序的情况对称处理。核心代码如下def search(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: return mid if nums[left] nums[mid]: # 左半段有序 if nums[left] target nums[mid]: right mid - 1 else: left mid 1 else: # 右半段有序 if nums[mid] target nums[right]: left mid 1 else: right mid - 1 return -1这个题的坑点在于边界条件是而不是。为什么因为当区间只有两个元素时比如[3, 1]left0, mid0此时nums[left] nums[mid]如果不加等号会误判“左半段有序”然后走向错误分支。加等号可以保证当nums[left] nums[mid]时也按照左半段有序处理反而能正确处理只有两个元素的情况。这个细节我是被测试用例教训过之后才彻底记住的。153. 寻找旋转排序数组中的最小值比搜索目标值更简单一点。它的核心思想是比较nums[mid]和nums[right]如果nums[mid] nums[right]说明最小值在右半段否则最小值在左半段或就是mid本身。因为要找最小值所以即使nums[mid] nums[right]也不能把right设成mid - 1而要设成mid否则可能会跳过最小值。这个逻辑刚好对应左闭右开写法的right mid模式用起来很自然。3.3 二维矩阵与双数组74 与 474. 搜索二维矩阵表面上是一个二维题实际上可以把它“拉直”成一维因为矩阵的每一行从左到右递增并且下一行的第一个元素大于上一行的最后一个元素所以整个矩阵按行拼接后就是一个有序数组。于是直接用一维二分即可只需要做一次坐标映射def searchMatrix(matrix, target): m, n len(matrix), len(matrix[0]) left, right 0, m * n - 1 while left right: mid left (right - left) // 2 mid_val matrix[mid // n][mid % n] if mid_val target: return True elif mid_val target: left mid 1 else: right mid - 1 return False这道题的难点不是二分而是“把一个有序的二维结构映射到一维坐标”。mid // n是行号mid % n是列号这个映射关系想明白了代码就是套模板。面试时如果能把这道题的思路讲清楚基本能给面试官留下“这人是真的理解二分而不是背题”的印象。4. 寻找两个正序数组的中位数是二分里比较难的一道也是 hot100 的常客。这题如果用合并数组再取中位数的方法时间复杂度是O(mn)但题目要求O(log(mn))于是只能用二分。核心思路是在两个数组中分别划分割线i和j使得左半部分元素总数等于右半部分或左半比右半多一个并且左半部分的最大值不超过右半部分的最小值。通过二分调整i的位置同时j根据i自动确定因为存在关系i j (mn1)//2。这道题的代码细节非常多包括奇偶长度处理、一个数组为空、以及越界访问的保护。我建议初学者先不要死磕4把它放到后期进阶。热词里提到的leetcode 1273和三维接雨水这类难题也都适合在基础二分彻底掌握之后再碰。3.4 二分答案类875 与 1011二分答案也叫“对答案二分”是力扣近两年特别喜欢考的题型875. 爱吃香蕉的狒狒就是最经典的入门题之一这题在热词里也出现了。题目给了一堆香蕉堆piles和一个时限h让你求“在 h 小时内吃完所有香蕉的最小速度k”。如果直接求最小速度你可能会想用贪心、模拟但一个一个试速度太慢。而这里的关键性质是速度k越大吃完所需时间越短满足“时间 h”这个条件的速度值在数轴上是单调的——速度太小不满足速度足够大一定满足。既然具备单调性就可以在速度范围[1, max(piles)]上做二分不断试探当前的mid速度是否能在时限内吃完。判断函数是核心需要单独写一个辅助函数def can_finish(piles, h, speed): total_hours sum((p speed - 1) // speed for p in piles) return total_hours h def minEatingSpeed(piles, h): left, right 1, max(piles) while left right: mid left (right - left) // 2 if can_finish(piles, h, mid): right mid # 速度快了或刚好尝试缩小 else: left mid 1 # 速度慢了必须加大 return left这里的取整方式要留意(p speed - 1) // speed是向上取整表示每一堆需要吃多少小时不能直接用p // speed否则会少算时间。另外这题用left right的模板更合适因为我们要找的是“可行域的左边界”right mid保留了候选答案不丢left mid 1排除掉不可行的值。同类型的题还有1011. 在 D 天内送达包裹的能力、410. 分割数组的最大值它们都是用二分答案把“求最小值”问题转化为“判断某个值是否可行”问题。一旦掌握这个套路你会突然发现很多看似毫无头绪的困难题都有了统一的解题抓手。4. 二分查找的变形套路与高频易错点排查4.1 lower_bound 与 upper_bound面试手撕重灾区力扣34. 在排序数组中查找元素的第一个和最后一个位置问的其实就是lower_bound和upper_bound。很多人在这个题上栽跟头是因为试图用一次二分同时找到左边界和右边界结果逻辑纠缠不清。我的建议是写两个辅助函数一个找第一个 target 的位置一个找第一个 target 的位置最后一个等于 target 的区间就是[lower_bound, upper_bound - 1]。用左闭右开模板写这两个函数会非常顺def lower_bound(nums, target): left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: left mid 1 else: right mid return left def upper_bound(nums, target): left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: left mid 1 else: right mid return left两个函数唯一的区别是lower_bound判定条件用 target移动左指针upper_bound用 target移动左指针。这种写法之所以不容易出错是因为right mid意味着mid仍然有可能是答案我们只是把右边界收缩到mid处继续探索不会丢失候选值。想通这一点你就再也不会为 left/right 到底要不要1而纠结了。4.2 死循环、越界与中点选择三大经典坑二分查找初学阶段最容易踩的坑有三个我一个个说。第一个是死循环。死循环的根源是left和right更新不合理导致某一个位置被无限重复检查。比如在左闭右闭模板里如果查到nums[mid] target后写left mid而不是left mid 1当left和right相邻时mid永远是left左指针永远不动程序就卡死了。解决办法很简单每轮循环必须使区间长度严格缩小所以排除mid时要1或-1。第二个是数组越界。这个在34和4这类题里特别常见。比如34题中如果所有元素都小于targetlower_bound返回len(nums)直接用它去访问nums[left]就会越界。所以查找前要做一次lower_bound len(nums) and nums[lower_bound] target的判断缺一不可。这个细节我见过太多人写漏。第三个是中点选择。mid left (right - left) // 2是向下取整// 2换成(right - left 1) // 2是向上取整。在普通二分里两种都行但在需要配合left mid或right mid的模板里选错方向会触发死循环。我的经验是如果代码里出现left midmid就必须向上取整如果出现right midmid就向下取整。这是一条很好用的口诀能帮你快速排查死循环问题。4.3 判定函数的单调性能不能用二分的关键最后再说一个很多教程没有强调的点写二分答案题之前先问自己一句判定函数check(mid)真的单调吗如果答案区间不是单调的二分就会给出错误结果。举个例子假设有个问题要你求某个值但这个值“太高也不行、太低也不行”在中间某段才可行那就不是单调函数而是分布函数不能用普通二分。通常需要把问题转换成“找最大的不满足”、“找最小的满足”这类带方向性的问题才可以用二分。热词里提到的三维接雨水、复杂树形结构题目如果要用二分都是因为问题本身可以剥出一层单调性来。判断单调性的实操方法是随手画一个草图横轴是mid候选答案纵轴是判定结果True/False。如果真值分布是False...False True...True那就可以用二分找分界点如果出现True False True这种多段分布就得想别的办法了。掌握这个分析习惯能少走很多弯路。5. 从 hot100 到周赛二分查找刷题路线与扩展方向5.1 力扣热题100的二分题目顺序推荐如果你现在打开力扣热题100想把二分的题刷一遍我建议按下面的顺序来不要跳704. 二分查找背熟模板理解左闭右闭和左闭右开的区别。35. 搜索插入位置练习 lower_bound 思想把模板改造成“返回第一个大于等于”的写法。34. 在排序数组中查找元素的第一个和最后一个位置练习同时写 lower_bound 和 upper_bound。74. 搜索二维矩阵练习一维坐标到二维矩阵的映射。33. 搜索旋转排序数组理解“二段性”学会在局部有序段中二分。153. 寻找旋转排序数组中的最小值进一步训练边界处理。875. 爱吃香蕉的狒狒正式进入二分答案的领域。4. 寻找两个正序数组的中位数进阶题学有余力再上。这个顺序不是随便排的它遵循“基础模板 - 边界变形 - 结构变形 - 思维模型变形”的递进。我发现很多读者直接刷33和4刷到怀疑人生其实就是因为前面的基础能力还没夯实。5.2 周赛与 hot100 之外如何用二分思想扩展解题视野热词里的leetcode周赛430和leetcode 1273让我想到一个常见问题很多人把二分题限制在“数组题”标签里遇到树、图、字符串就想不到二分。实际上二分的本质是“答案空间上的搜索”所以它可以出现在任何题型里。比如树上的某些“第 k 大”问题可以先二分答案再做一次树形 DP 或遍历来判断是否可行再比如热词里提到的 fpga 二分查找树编码器这是硬件设计里用二分树结构优化查找路径的思路和软件二分的决策过程异曲同工。我自己的习惯是每周参加一次力扣周赛不管能不能全做出来都刻意训练自己“看一道题先问单调性”。如果一道题能转化为“给定 x判断是否可行”我就倾向于用二分答案来解。这个习惯让我在遇到陌生题型时不至于完全没思路至少有一个通用的突破口。5.3 给你的刷题记录表与复盘方法最后分享一个我自己整理的二分题复盘表建议你在本地维护一份题号题型分类使用模板核心易错点是否掌握704基础查找左闭右闭终止条件是35lower_bound左闭右闭返回 left是34边界查找左闭右开越界判断否33旋转数组左闭右闭等号细节复盘153旋转数组左闭右开right mid复盘74二维映射左闭右闭坐标换算是875二分答案左闭右开向上取整否4进阶二分自定义奇偶处理否每次刷完一道题想一想“如果我把题目条件改一下还能不能用同样的方法”比如 704 改成“有重复元素”你就应该联想到 3433 改成“允许重复元素”你需要思考怎么跳过相同值避免left right失效。这种改编训练比盲目刷新题更能加深对二分的理解。我自己带过的不少读者一开始也是各种边界 bug 不断后来坚持“每道题必须写清楚循环不变量并解释为什么更新 left/right”一段时间后正确率高了很多。说白了二分查找不是靠天赋而是靠一套清晰的思维框架加刻意练习。最后再分享一个我踩过多次坑之后养成的习惯提交代码前先拿一个长度为 1 的数组、一个长度为 2 的数组、以及 target 在数组左边界/右边界/不存在这几种极端用例在脑子里跑一遍。二分题 90% 的错误都藏在这些极端情况里提前过一遍能省下不少提交失败的挫败感。希望你也能借助这套思路把力扣上的二分题稳稳拿下。