从真正开始认真刷力扣到现在我最大的一个感触是二分查找是所有“看似简单”的题里翻车率最高的一类。LeetCode 上一堆简单题标注着“Easy”但你要是直接上手写二分边界稍微一含糊不是死循环就是越界要不就是结果差一位。尤其是热题 100 里那几道二分变种题像 875 爱吃香蕉的狒狒、1011 在 D 天内送达包裹的能力多少人在“答案二分”这一步卡住。这篇文章我打算把自己刷二分查找力扣题的经验一次性倒出来从最基础的循环不变量讲起到左右边界模板、答案二分套路再配合几道力扣高频题的完整推导过程最后给一份我自己的调试方法和防坑清单。不管你是刚接触力扣的新手还是刷了百来题但二分总是模棱两可的老手这篇应该都能让你把二分这块一次性焊死。1. 为什么二分查找代码看着简单却总是写错很多初学者背模板背得很熟left 0, right len(nums) - 1然后while left rightmid (left right) // 2。这代码看起来没毛病可一旦换个题目比如找左边界、右边界、找峰值、找旋转数组最小值同样的模板改两行就开始出错。问题出在哪出在大多数人没有真正理解“循环不变量”。1.1 你背的是模板不是边界规则二分查找的核心不是“折半”这个动作而是每一轮循环之后你要找的目标值一定还在某个明确的区间里。这个区间就是循环不变量。这里有两个常见区间定义左闭右闭[left, right]每一轮循环开始时目标值如果存在一定在nums[left]到nums[right]之间包含两端。所以初始right len(nums) - 1循环条件是while left right。当nums[mid] target时说明目标值不可能在mid及右边所以right mid - 1。左闭右开[left, right)每一轮循环开始时目标值如果存在一定在nums[left]到nums[right-1]之间包含左端不包含右端。初始right len(nums)循环条件是while left right。当nums[mid] target时right mid而不是mid - 1因为right本身就是开区间不需要排除mid位置的元素。这两种写法没有谁绝对好但你必须选定一种并坚持到底。我最常见到的翻车场景是初始化用的左闭右闭收缩边界的时候却按左闭右开写或者反过来。只要区间定义和收缩规则不匹配结果必然错。1.2 死循环的本质是区间没有严格缩小还有一个高频翻车点死循环。很多人以为死循环是while条件写反了其实本质是某一轮循环之后区间大小没有变小。举个经典例子# 错误示范left mid 导致的死循环 def binary_search(nums, target): left, right 0, len(nums) - 1 while left right: mid (left right) // 2 if nums[mid] target: left mid # 问题在这target 可能在 mid 位置吗 else: right mid return left if nums[left] target else -1假设nums [1, 3]target 3。第一轮left0, right1, mid0nums[0]1 3于是left mid 0。第二轮left0, right1, mid0又执行left mid 0。循环永远出不去。这个例子的坑在于当区间只剩两个元素mid算出的是左元素如果你把left更新成mid而mid又恰好等于原来的left那区间就原地踏步了。那么正确做法是什么得分析nums[mid] target这个条件。如果nums[mid]严格小于target那mid这个位置肯定不是目标值所在的位置所以可以安全地left mid 1。这就是区间严格缩小的关键每次更新边界时必须把已经排除掉的 mid 位置剔除出区间。1.3 死循环自查方法如果你写了一个二分运行起来超时先别急着查业务逻辑直接看三件事循环条件用的是还是跟你的区间定义匹配吗left的更新会不会出现left mid且mid left的情况区间长度为 0 或 1 时你的代码能正确退出吗我个人的习惯是在 while 循环第一行打印left, right, mid跑一个小样例一眼就能看出区间有没有在缩小。真不是丢人的事刷题阶段靠打印找 bug 比对着屏幕干瞪眼快十倍。2. 左闭右开模板一套代码适配力扣绝大多数二分题前面说了两种区间定义我推荐大家主用左闭右开。为什么因为 Python 的bisect模块、C 的 STLlower_bound / upper_bound全是左闭右开语义刷题用这套和标准库保持一致不容易记混。2.1 标准模板找第一个不小于 target 的位置这是所有二分查找里最核心的模板力扣的 35 题搜索插入位置就是直接考这个def lower_bound(nums, target): left, right 0, len(nums) # 左闭右开[0, len(nums)) while left right: mid left (right - left) // 2 if nums[mid] target: left mid 1 else: right mid return left这个函数返回什么返回第一个满足nums[i] target的下标 i。如果所有元素都小于 target返回len(nums)。你可能会问为什么nums[mid] target时是left mid 1而nums[mid] target时是right mid这就是循环不变量的体现当nums[mid] target说明包括mid在内的左边这一段都小于 target不可能是第一个不小于 target 的位置直接排除所以left mid 1。当nums[mid] targetmid这个位置可能是答案也可能是答案右边但答案绝不可能在mid右边所以把右边界收到mid注意是开区间所以right mid表示新的搜索范围是[left, mid)。这个模板用熟了之后很多题都只是在这个基础上套壳。2.2 mid 计算的溢出问题我看到网上很多题解写mid (left right) // 2在 Python 里这没问题因为 Python 整数是无界的。但如果你用 C 或 Java 刷题left right可能溢出 int 范围。所以我习惯统一写成mid left (right - left) // 2这个写法在所有语言里都安全而且跟(left right) // 2算出来的结果完全一样只是数学上等价变形了一下。养成这个习惯以后写 C 的时候就不用特意改。还有一个细节mid到底是取左中位数还是右中位数。在左闭右开模板里mid left (right - left) // 2取的是左中位数即靠左的那一个。当区间只有一个元素时mid left这时候如果你写left mid就会死循环。所以左闭右开模板里凡是left的更新必须是mid 1只有right才能更新成mid。这个理解和前面 1.2 的死循环案例是对应的。2.3 用 lower_bound 模板直接解决 35 题力扣 35 题给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。这题就是裸的lower_bounddef searchInsert(nums, target): return lower_bound(nums, target)比如nums [1,3,5,6], target 5lower_bound返回 2target 2返回 1target 7返回 4插到末尾。这个题虽然简单但它帮我们建立了一个很重要的思维“查找”可以等价为“找第一个满足某条件的位置”。这个思维后面会反复使用。3. 左右边界问题从“找一个”到“找一段”力扣 34 题在排序数组中查找元素的第一个和最后一个位置是二分查找里的一道关键分水岭题。很多人做过 704裸二分和 35插入位置但一到 34 就开始懵因为目标值可能重复需要同时找左边界和右边界。3.1 左边界就是 lower_bound找第一个等于 target 的位置其实就是找第一个不小于 target 的位置def find_left(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之后判断一下left len(nums) and nums[left] target如果不成立说明 target 不存在。3.2 右边界两个思路找最后一个等于 target 的位置有两个主流思路思路一找第一个大于 target 的位置减一。def find_right(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 - 1这里把条件改成nums[mid] target意味着我们找的是“第一个大于 target 的位置”这个位置的前一个就是最后一个等于 target 的元素。思路二分别用两个模板一个找下界一个找上界。有的同学喜欢把“最后一个等于 target”也用一个独立的模板来写这也没问题但我觉得“找大于 target 的位置再减一”更不容易记混因为它还是在用同一个 lower_bound 核心。3.3 34 题完整代码左闭右开def searchRange(nums, target): 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 start lower_bound(nums, target) if start len(nums) or nums[start] ! target: return [-1, -1] end lower_bound(nums, target 1) - 1 return [start, end]看到了吧找右边界根本不需要再写一个上界模板直接对target 1调lower_bound然后减一就是右边界。这个技巧我在很多题里都用到过比如统计有序数组中某个数出现的次数就是lower_bound(target 1) - lower_bound(target)。这就是为什么我前面强调“一套模板打天下”——你不需要背三个四个模板把lower_bound这一个吃透左右边界问题只是它的组合应用。4. 从“查找”到“判定”答案二分才是二分的高阶用法刷到力扣热题 100 的后半段你会遇到一类很特别的二分题题目里根本没有给你一个有序数组让你查找而是让你求一个“最小速度”“最少天数”“最小力气”。这类题的典型代表就是 875爱吃香蕉的狒狒和 1011在 D 天内送达包裹的能力。我第一次看到 875 题时完全没意识到这是二分因为题目描述是一个猴子吃香蕉的场景有一堆香蕉piles[i]狒狒每小时最多吃k根如果一堆少于 k 根就吃完这一堆然后等下一小时问最少用多大的速度能在h小时内吃完。直觉上这是一个模拟题但h和piles[i]的范围都是 10 的 9 次方级别显然不能一个一个速度去试。这里就需要一个思维跃迁把“求最优解”变成“验证某个解是否可行”然后在可行解的范围内二分。4.1 先把判定函数写出来所谓二分答案核心是两步先确定答案的单调范围。比如 875 题速度k的范围是[1, max(piles)]因为速度至少是 1最多是最大那一堆的香蕉数如果比最大一堆还大每小时也只能吃一堆再大没有意义。写一个判定函数can_finish(k)判断在速度k下能不能在h小时内吃完。875 题的判定函数长这样def can_finish(piles, k, h): hours 0 for p in piles: hours (p k - 1) // k # 上取整 if hours h: return False return hours h注意这里(p k - 1) // k是“p 除以 k 后向上取整”的经典写法。因为狒狒吃一堆香蕉如果一根都没剩下也要算一个完整的小时所以必须上取整。4.2 在答案空间里做二分判定函数写好之后主函数就非常套路了def minEatingSpeed(piles, h): left, right 1, max(piles) while left right: mid left (right - left) // 2 if can_finish(piles, mid, h): right mid # 能吃完尝试更小的速度 else: left mid 1 # 吃不完必须加速 return left这里你发现没有整个二分查找的对象不再是数组里的元素而是一个“速度值”的连续整数区间。我们把“速度 k 能否在 h 小时内吃完”看成一种单调的布尔函数k 越大越可能吃完。于是问题就变成了“找第一个满足 can_finish(k) 为 True 的 k”——这本质上就是 lower_bound。4.3 1011 题的套路完全一样1011 题在 D 天内送达包裹的能力给定一个包裹重量数组weights传送带每天最多装一定载重capacity的货品求能在 D 天内送完的最小载重。这个题的答案空间是[max(weights), sum(weights)]因为载重至少得能装下最重的一个包裹至多一天把所有包裹全装走。判定函数也很直观def can_ship(weights, capacity, days): cur 0 d 1 for w in weights: if cur w capacity: d 1 cur 0 if d days: return False cur w return d days主函数同样是一个 lower_bound 模板def shipWithinDays(weights, days): left, right max(weights), sum(weights) while left right: mid left (right - left) // 2 if can_ship(weights, mid, days): right mid else: left mid 1 return left这类题的共同特征非常明显题目要求的是一个“最小可能值”而这个“值”的可行性是单调的。你只要把判定函数写对二分骨架根本不用动。这就是“答案二分”这个套路最大的价值——它的代码骨架高度统一唯一要动脑的地方全在判定函数里。5. 旋转数组与峰值二分不只用在有序数组上很多教材告诉你“二分查找只能用在有序数组”这其实是个巨大的误解。力扣里有两类高频题专门打破这个认知搜索旋转排序数组33 题和寻找峰值162 题。5.1 搜索旋转排序数组利用部分有序收缩区间33 题的场景是一个升序数组在某个未知位置旋转了比如[4,5,6,7,0,1,2]让你在这个数组里找 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判断nums[left] nums[mid]为 True说明从left到mid是严格递增的这时候只需要看 target 在不在这个递增区间里。如果在就按普通二分收缩如果不在那 target 只可能在另外一半。这个做法的核心还是利用“局部有序”来排除一半的搜索空间。注意这个判断里用的是nums[left] nums[mid]不是。原因是当数组只有两个元素时mid可能等于left用等号保证进入左半有序的逻辑分支避免漏判。5.2 寻找峰值比较相邻元素决定往哪走162 题要求在一个数组中找一个峰值即nums[i] nums[i1]且nums[i] nums[i-1]数组两端默认为负无穷。这题在很多人的直觉里根本不该用二分因为数组无序。但题目有个隐含条件任意相邻元素都不相等。考虑mid位置的元素如果nums[mid] nums[mid 1]说明mid处于一个上升段峰值一定在mid右边因为右边至少有一个上升趋势最终要么遇到下降要么到达数组末尾而末尾视为负无穷所以一定会出现峰值。如果nums[mid] nums[mid 1]说明mid处于一个下降段峰值可能在mid左边也可能就是mid自己。于是可以写出def findPeakElement(nums): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] nums[mid 1]: left mid 1 else: right mid return left这个写法就是标准的 lower_bound 模板只不过“判定条件”从nums[mid] target换成了nums[mid] nums[mid 1]。这再次印证了前面说的模板不重要重要的是你理解每一步收缩背后的单调性依据。5.3 LeetCode 热题 100 里的二分类题目该怎么刷如果你在按“力扣热题 100”刷题我建议按下面这个顺序来逻辑上是层层递进的题目核心考点难度704. 二分查找最基础的二分模板热身简单35. 搜索插入位置lower_bound 模板简单34. 在排序数组中查找元素的第一个和最后一个位置左右边界组合应用中等33. 搜索旋转排序数组部分有序区间的二分中等162. 寻找峰值通过趋势判断收缩方向中等153. 寻找旋转排序数组中的最小值部分有序的另一种形式中等875. 爱吃香蕉的狒狒答案二分 / 判定函数中等1011. 在 D 天内送达包裹的能力答案二分 / 判定函数中等这个顺序的好处是前四题帮你把“查找型二分”的边界彻底搞明白第五第六题让你理解二分对“部分有序”同样有效最后两题带你跨入“答案二分”的门槛。我见过很多刷题群的人一上来就刷 875结果判定函数写不明白卡了一下午最后连二分模板都开始怀疑。但如果你先把 35 和 34 写透875 其实就是套一层壳。6. 二分查找调试三板斧打印、断言、边界样本这一章我不讲算法讲点实打实的“工作流”。刷题和写工程代码不一样你没有足够的日志系统和单测框架但二分这种代码恰恰最容易因为边界问题翻车。我在刷题初期踩坑无数后来总结了一套自己的调试三板斧分享给大家。6.1 打印三元组left、right、mid当你怀疑自己的二分死循环或者边界不对时第一步就是在 while 循环开头打印while left right: mid left (right - left) // 2 print(fleft{left}, right{right}, mid{mid}, nums[mid]{nums[mid]})用一个最小样例跑一遍。比如nums [1, 3]。如果打印出来发现某两轮left和right完全没变化那基本就是死循环你立刻能看到是哪一行赋值导致区间没有缩小。这个打印方法对答案二分的题目同样适用你可以打印 mid 和can_finish(mid)的结果能直观看到判定函数返回值的单调性是否符合预期。6.2 断言区间单调性如果你用的是左闭右开模板有一个铁律可以写成断言放进去辅助验证# 左闭右开模板中left 每次更新后必须满足 left right assert left right很多时候二分 bug 不是方向搞反而是某次更新后 left 跑到了 right 右边程序直接返回一个越界或者错误结果。加一行断言立刻暴露问题。6.3 边界测试样本清单每次写完二分无论题目多简单我都会用下面这些样本自测一遍空数组nums []单元素数组nums [5]两元素数组nums [1, 3]目标值在开头target nums[0]目标值在结尾target nums[-1]目标值不存在比所有元素都小 / 大 / 介于中间全相同元素nums [2, 2, 2, 2, 2]这些测试用例基本覆盖了所有边界分支。尤其是全相同元素这个用例很多人会漏测一旦漏了34 题那种左右边界题很容易写错。6.4 我踩过的二分大坑最后分享两个我自己真实踩过的坑给大家打个预防针。第一个坑把right mid和right mid - 1搞混。在左闭右开模板里right是开区间边界它本身指向的元素不会参与下一轮搜索所以当nums[mid] target时应该right mid把mid排除出去。但如果你还在用左闭右闭的习惯写right mid - 1就会把mid这个可能是答案的位置也丢掉了结果多搜一圈返回错误下标。第二个坑答案二分的范围没取对。875 题有人把right设成max(piles) 1或者干脆设一个 10 的 9 次方导致多算了 log(10^9) 轮循环虽然不至于超时但代码缺乏解释力。更严重的是 1011 题有人把left设成 1然后判定函数里对小于最大包裹重量的 capacity 还要做特殊处理这完全是给自己挖坑。记住一句话答案范围的下界和上界必须是判定函数的天然边界而不是拍脑袋来的。7. 二分查找的进阶思考与刷题心得写到这里二分查找的基本框架、模板应用、变体套路都已经覆盖了。最后我想聊一点更深的东西也是我刷完这些题之后对二分本身的理解。7.1 二分本质是“单调性搜索”不是“有序数组搜索”很多人学二分时被“有序数组”四个字限制住了导致遇到旋转数组、峰值、答案二分这类题时完全反应不过来。但一旦你意识到二分的本质是在一个存在“序关系”的搜索空间里通过排除一半来逼近答案你就能在更多场景下使用它。什么是“序关系”不一定是数值升序也可以是“条件满足与否”的单调变化。比如“速度 k 能否吃完所有香蕉”这个布尔值随 k 增大从 False 变 True是单调的“天数 d 内能否运完所有包裹”也是单调的。只要你的搜索空间具备这种“单调布尔性质”二分就可以用。7.2 单调性与 log 的直觉为什么二分能到 O(log n)因为每轮都排除一半。这个直觉很多人有但没有真正内化。当你遇到一个问题搜索空间有 n 个可能答案如果你能设计出一个单调判定函数那么你不需要逐个尝试只需要 log(n) 次判定。在很多真实的工程场景里这个优化是数量级的差距。我记得自己做 875 题时的第一版暴力解法是从速度 1 一直试到 max(piles)最坏情况要试 10^9 次。改成二分后最多 log2(10^9) ≈ 30 次判定每次判定扫一遍 piles 数组。如果 piles 有 10^4 个元素那就是 30 万次操作暴力却要 10^13 次完全不是一个量级。7.3 力扣周赛中的二分规律如果你关注力扣周赛比如最近的热搜词里有“leetcode周赛430”你会发现二分在周赛里的出现频率相当高。它很少单独出现更多是作为某个大问题的一个子步骤。比如一道题需要你求“最小满足 xx 条件的值”前面铺垫了几百字的场景最后的数学模型就是二分答案。这正是为什么很多刷题经验贴都强调“二分是必须掌握的底层能力”——它不是难点但它是一道难题的骨架。骨架上要长什么血肉贪心、动态规划、DFS那是另一回事但骨架本身立不住后面全白搭。我个人刷题的习惯是每遇到一个二分题不管 AC 不 AC都会把它的“判定函数”单独摘出来看看这个判定函数是什么样的扫描逻辑它的复杂度是多少如果我能把判定函数从 O(n) 优化到 O(log n)那整个算法的复杂度会降多少这个习惯帮助我建立了很多“算法直觉”后来做工程时遇到性能问题也能更快定位到“这里可以用单调性做二分”的机会。7.4 相关高频题的横向对比除了上面详细展开的题目还有一些 LeetCode 高频二分题值得大家自己动手推一遍153. 寻找旋转排序数组中的最小值本质是找“第一个小于等于末尾元素的位置”和 33 题共享一套“部分有序”的推理逻辑。4. 寻找两个正序数组的中位数这题偏难但它的二分思路是“在两个数组里分别排除前 k/2 个元素”属于二分的高级变体面试里遇到概率不低。69. x 的平方根裸的答案二分搜索范围[0, x]判定条件是mid * mid x。适合拿来巩固答案二分的基本功。278. 第一个错误的版本纯 lower_bound 模板连判定函数都是现成的isBadVersion(mid)。很适合作为入门练习。如果你能把 875、1011、153、33 这四道题吃透再去碰 4 题中位数会比直接硬啃轻松得多。因为你的心里已经有了“单调判定”“部分有序”“排除一半”这些思维框架剩下的只是把它们组合起来。我自己刷二分最大的体会是这玩意儿不能靠记忆得靠推导。每次写的时候在心里把循环不变量的区间画一遍比背十套模板都管用。尤其是当你从简单题过渡到中等题、从查找型过渡到答案二分型时你会发现所有题目殊途同归——无非就是回答三个问题搜索范围是什么判定函数是什么答案落在哪个边界上把这三个问题回答清楚了代码自然就出来了。