从三个月前决定认真刷题开始我给自己定的目标是每天至少两道LeetCode周末复盘总结按“面试经典150”清单推进。今天到了day73正好刷完这个清单里的二分查找专题进度条来到2.1的节点。说实话这批题目给我最大的感受是二分查找远不止“写个while循环”那么简单它考察的是你对边界条件、单调性、答案空间的理解深度。这篇就把我这段时间整理出来的二分查找完整思路、具体题目的拆解过程以及踩过的坑一并分享出来给正在刷题或者准备面试的朋友一个参考。1. 为什么“面试经典150”值得按专题刷市面上的刷题清单很多热门100题、剑指Offer、周赛题解、各种企业面经汇总但“面试经典150”这份清单的优势在于它按数据结构和算法专题做了系统分类而不是简单堆题。对于准备面试的人来说这种组织方式非常友好因为它逼着你把一个专题吃透而不是东一榔头西一棒子。1.1 专题刷题比随机刷题高效在哪里我刚开始刷题的时候也走过弯路按题号从前往后刷结果就是今天做一道链表、明天做一道动态规划思维切换成本很高而且每个专题刚摸到一点门道就跳走了下次再遇到同类型的题还是发懵。按专题刷题的好处有三个思维模式可以连续构建。连续一周只做二分查找你自然会把“有序数组找目标”“答案值域二分”“极大极小化问题”这些范式在脑子里串起来。边界条件和易错点在短期内反复出现记忆更深刻。比如二分查找里的mid取值、左右指针更新逻辑连着做三五道题之后就会形成肌肉记忆。面试时更容易举一反三。面试官出题往往是从一个基础题往深处延伸专题化训练正好匹配这种考察方式。1.2 2.1这个阶段在整个清单中的位置“面试经典150”大体按数组、字符串、链表、树、图、动态规划等专题排列我在day73进入的是二分查找专题这是数组大类下的一个核心分支。之所以叫“2.1”是因为这是该专题下的第一批核心题目主要包括最基础的二分查找模板、搜索插入位置、爱吃香蕉的狒狒这类经典题。按我个人的进度安排day73能到这个位置说明前面的基础专题打得还算扎实。数组的双指针、滑动窗口、哈希表这些内容在二分查找里都会用到所以前期的积累在这个阶段会直接体现出来。2. 二分查找的核心不是在数组里找而是在答案里找很多人对二分查找的理解停留在“在一个有序数组里找一个数”这导致一旦题目稍微变形就不知道怎么用。实际上二分查找的应用范围远不止于此。只要你发现问题的答案落在一个明确的区间内并且这个区间具有单调性某个条件在答案的一侧为真、另一侧为假就可以用二分查找来解决。2.1 经典模板的三种写法先看最基础的二分查找模板。假设在一个有序数组中查找目标值target常见的写法有三种。第一种左闭右闭区间[left, right]def binary_search(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid - 1 return -1第二种左闭右开区间[left, right)def binary_search(nums, target): left, right 0, 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第三种在答案值域上二分这个后面会重点讲。第一种写法最直观left right表示区间内还有一个元素需要检查所以循环结束后left是第一个大于target的位置right是最后一个小于target的位置。第二种写法是Python社区比较推崇的风格[left, right)的区间定义让right指针本身不包含在待查范围内所以当nums[mid] target时直接让right mid即可不需要减一。我个人在实际刷题中更推荐用第二种左闭右开的写法因为它的区间定义清晰在处理“寻找左边界”“寻找右边界”这一类变体时只需要微调条件就行不容易出错。2.2 为什么 mid 要写成left (right - left) // 2很多初学者会写成(left right) // 2这在大多数情况下没问题但当left和right都很大时left right可能溢出整数范围。虽然Python的整数是任意精度的不会真的溢出但这是一个良好的编码习惯而且在Java、C这些语言里是必须注意的。另外mid是向下取整还是向上取整也是有讲究的。在标准的“找target”场景中向下取整足够了。但在某些需要避免死循环的场景中比如寻找左边界时如果left和right相差1向下取整会让mid等于left如果你在这个分支里又执行了left mid就会造成死循环。这种情况需要让mid向上取整也就是mid left (right - left 1) // 2。注意这个细节是二分查找最常见的坑之一。记住一个口诀left mid时mid要向上取整right mid时mid向下取整即可。2.3 关键理解二分的是“可能性”而不是“下标”来个生活化的类比。假设你是一个老师手里有一摞按学号排好的学生试卷你要找出学号正好是20240001的那张。你当然可以一张一张翻但更聪明的方式是直接翻开中间那张看看学号是大于还是小于目标然后丢掉一半。这就是在有序数组上二分。但现在换一个问题假设你要批改这摞试卷你希望找到一个“及格分数线”使得及格人数恰好等于20人而分数越高及格人数越少。这个“分数线”的取值是从0到100之间的任意整数而且随着分数线提高“及格人数是否大于等于20”这个条件会出现从真到假的单调变化。这时候你同样可以二分但二分对象不是某个数组下标而是答案本身。LeetCode上的很多二分题比如“爱吃香蕉的狒狒”“分割数组的最大值”“每个厨师做菜的最短时间”本质上都属于后者。如果能意识到这一点你的二分查找水平会提升一个档次。3. 核心题目拆解从模板到实战目标150清单里的二分题目并不算多但每道都值得反复咀嚼。我挑几道代表性强的题目把完整的思考过程写下来。3.1 搜索插入位置最简单的二分变体题目要求在一个有序数组中找目标值如果存在返回下标不存在返回应该插入的位置。LeetCode编号35。这题的思路其实一句话就能说清二分查找结束后left指向的位置恰好就是插入位置。我用了左闭右开的模板def searchInsert(nums, target): left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: right mid else: left mid 1 return left这里的关键点是把“找到target”和“找不到target”统一处理。条件写成nums[mid] target表示我们要找的是第一个大于等于target的位置。如果target存在返回的就是它第一次出现的位置如果不存在返回的就是它应该插入的位置。这个写法比先查找再判断的写法简洁得多而且逻辑上更符合“插入位置”的定义。3.2 爱吃香蕉的狒狒在答案上二分的经典入门这道题在热搜词里出现了说明热度确实高。题目本身很有意思狒狒有N堆香蕉第i堆有piles[i]根香蕉狒狒每小时最多吃K根但她每小时只选择一堆香蕉进食如果这一堆少于K根她吃完这一堆后这小时就结束了不会去动下一堆。现在要求在H小时内吃完所有香蕉求最小速度K。这个题的暴力解法是从K1开始逐个尝试最小的满足吃完时间 H的K就是答案。但K的取值范围是1到max(piles)最大可能是10^9级别逐个尝试在数据量大的时候会超时。而“吃完时间是否小于等于H”这个条件关于K是单调的K越大所需时间越少。所以可以直接在K的取值范围上二分。核心在于计算给定速度K时所需的总时间def can_finish(piles, H, K): total_time 0 for p in piles: total_time (p K - 1) // K return total_time H(p K - 1) // K是向上取整的写法。比如一堆有10根K3那么这一堆需要4小时3331用这个公式算出来就是(10 3 - 1) // 3 12 // 3 4完全正确。然后在外层二分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这里left mid 1配合right mid用的是“寻找最小满足条件的值”的标准二分框架。比赛里这道题的正确率并不算高主要卡在两点一是没有意识到K是二分对象二是向上取整的计算写错。实操心得看见“最大最小”“最小最大”这类词第一反应就应该是二分答案。爱吃香蕉的狒狒、分割数组最大值、第K小的距离对全是同一个套路。3.3 在排序数组中查找元素的第一个和最后一个位置这道题LeetCode 34是面试高频题考察的是对二分边界条件的掌握。要求在一个有序数组中找出某个目标值的起始下标和结束下标如果不存在返回[-1, -1]。思路是分别写两个二分一个找左边界一个找右边界。找左边界def find_left(nums, target): left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: right mid else: left mid 1 return left找右边界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细心的朋友会发现find_left就是把搜索插入位置的代码原样搬了过来。它找到的是第一个大于等于target的位置如果这个位置的元素不等于target说明target不存在。find_right的思路类似但找的是第一个大于target的位置再减一这样得到的下标就是target最后一次出现的位置。整体代码如下def searchRange(nums, target): left_idx find_left(nums, target) if left_idx len(nums) or nums[left_idx] ! target: return [-1, -1] right_idx find_right(nums, target) return [left_idx, right_idx]这道题我推荐大家在白纸上自己推导一遍left和right的变化过程尤其是在nums[mid] target时left和right分别怎么移动。把这个过程想明白了二分的基本功就扎实了。4. 二分答案的进阶应用从模板到直觉对很多初刷者来说经典模板还能看得懂但一到“二分答案”就有点犯怵我怎么知道这道题应该二分我怎么确定二分出来的答案就是对的这两个问题不解决题目稍微变个形就无从下手。4.1 如何识别一道题适不适合二分答案我总结下来符合以下特征的问题基本都可以考虑二分答案问题的答案是一个确定的数值且落在某个容易确定的范围内。需要找到“满足某个条件的最小值”或“满足某个条件的最大值”。给定一个候选答案后能够用较快的复杂度去验证它是否满足条件。第三个特征很关键。理论上任何能用“逐项尝试验证”解决的问题都可以优化成“二分尝试验证”。区别只在于验证函数的复杂度是否能接受。举个例子。假设你要给一群人排座位希望找到一个“最小的相邻座位间距”使得所有人都能坐下。暴力思路是从间距1开始不断尝试每次检查能不能坐满。但如果间距范围是0到10000逐项尝试最多要验10000次。而二分只需要log2(10000)约14次验证效率天差地别。这个思路放到LeetCode上就是“分割数组的最大值”这类题。给定一个数组把它分成m段使每段和的最大值最小。先猜一个答案mid然后遍历数组看用mid作为每段和的上限时能否在m段以内装下所有数。如果能说明mid可能大了继续往小猜如果不能说明mid太小了得往大猜。4.2 实战分割数组的最大值完整推导题目编号LeetCode 410我拿它来讲清楚二分答案的完整流程。第一步确定二分的范围。答案的最小可能值是数组中的最大值因为每一段至少要包含一个数而这一段的累加和不小于这个数本身。答案的最大可能值是整个数组的和相当于只分一段。第二步确定条件函数。给定一个候选答案max_sum贪心地分段从头遍历数组累加当前段的和一旦超过了max_sum就把当前元素作为新一段的开头段数加一。最后判断段数是否小于等于m。def can_split(nums, m, max_sum): count 1 cur_sum 0 for num in nums: if cur_sum num max_sum: count 1 cur_sum num else: cur_sum num return count m第三步在值域上二分def splitArray(nums, m): left, right max(nums), sum(nums) while left right: mid left (right - left) // 2 if can_split(nums, m, mid): right mid else: left mid 1 return left这个题我做了三遍才彻底掌握。第一遍能看懂题解但自己写不出验证函数。第二遍能默写出来但没理解为什么答案一定落在[max(nums), sum(nums)]这个区间里。第三遍才真正想通max(nums)是下界是数学上必然的而sum(nums)是平凡上界二分框架保证了答案一定能收敛到那个临界点。4.3 为什么验证函数是二分答案的灵魂很多人把注意力放在二分的写法上但我刷下来最大的体会是二分答案的难点不在二分本身而在验证函数的设计。二分框架就那么几行背都能背下来但验证函数却需要你根据题目内容去设计而且这个设计的质量直接决定了算法的正确性和复杂度。设计验证函数的核心是在给定一个候选答案x的前提下用尽量简单的方式回答“是否满足条件”。在“爱吃香蕉的狒狒”里验证函数是“按速度K吃香蕉的时间是否不超过H”。在“分割数组”里验证函数是“以max_sum为段上限能否在m段内装完”。在“每个厨师做菜的最短时间”里验证函数是“给定时间T所有厨师在T内能做的菜是否不少于目标数量”。一个验证函数如果设计得好往往还带着贪心的影子因为它需要快速判断一个方案是否可行而不是真的构造出最优解。5. 刷题过程中的关键经验与踩坑记录两个月前我开始系统性刷二分专题时其实踩了不少坑有些坑甚至让我一度怀疑自己是不是太笨了。现在回头看这些都是用真金白银换来的经验写出来希望帮你少走弯路。5.1 死循环最常见的崩溃来源二分查找死循环的根源只有一个区间无法收敛。最常见的情况是left mid配合mid向下取整当left和right相差1时mid等于left然后left又被赋值为mid区间大小没有变化于是死循环。假设left 5, right 6使用向下取整得到mid 5 (6 - 5) // 2 5如果这个分支里执行left mid那么下一轮还是left 5, right 6永远出不去。解决办法有两个一是避免在需要left mid的场景中用向下取整改用向上取整mid left (right - left 1) // 2保证当left和right差1时mid等于right这样left会向右收敛。二是统一使用左闭右开区间模板因为它天然避免了这个问题。我在刷题过程中会把模板固定下来遇到变体题先套模板再微调而不是每次从头写一遍。这样能大幅降低出错概率。注意如果你在代码里看到了死循环不要急着改while条件先检查所有给left或right赋值的分支看是否可能出现区间无法缩小的路径。5.2 边界条件left、right的初始值怎么定初始值的设定直接影响二分的搜索空间最常见的错误有以下几种。第一种是初始区间太小把正确答案排除在外。比如“爱吃香蕉的狒狒”里有人把left设成0这在数学上是错的因为速度不可能为0。也有人把right设为piles的平均值但这样就会漏掉正确答案——因为狒狒每小时只能选一堆吃如果某一堆特别大所需速度必然大于平均值。第二种是初始区间太大导致二分次数过多。比如在“分割数组”里right的最大值就是数组总和如果设置成很大的常数二分次数就会白白增加虽然不影响正确性但影响效率。第三种是处理“不存在”的情况。比如在“搜索插入位置”里如果target比数组里所有元素都大left最终会等于len(nums)此时访问nums[left]就会越界。所以一定要先判断left是否越界再看nums[left]是否等于target。5.3 Python实现的小心机用None代替-1提升可读性在二分查找里很多模板会返回-1表示not found。但Python里更Pythonic的做法是直接返回None。这并不是什么性能优化而是让调用方的判断逻辑更清晰def find(nums, target): # ... return None # not found不过在LeetCode上有些题目要求返回-1有些要求返回插入位置所以还是得根据题目的要求来定不能为了风格牺牲正确性。5.4 刷题完了之后一定要复盘我在day73这天回头整理二分专题时发现一个现象那些我能完整复现的题都是当时花时间写了复盘文档的而那些只是看一遍题解就算过的题现在几乎全忘了。复盘不需要写很长的文章只需要在代码下面记几个要点这道题的核心考点是什么二分的对象是数组下标还是答案值域验证函数是什么样的边界条件有哪些坑下次遇到类似题目时快速翻一下这些要点记忆会被重新激活。6. 二分查找在真实面试中的考察方式刷题最终还是要回归到面试。LeetCode上的“面试经典150”之所以叫这个名字是因为它里面的题目对应着面试中最常出现的算法原型。我结合自己参加过的面试和别人分享的面经聊聊二分查找在真实面试中的常见考察方式。6.1 从基础题出发的层层追问面试官通常不会直接甩一道二分模板题而是从一个简单场景出发逐步加约束条件考察你的应变能力。比如经典的“猜数字”问题猜一个1到n之间的数字每次猜完会告诉你大了还是小了最少猜几次一定能猜中这题就是裸的二分的商业化包装。但你回答完之后面试官可能会追问如果这个数字不是均匀分布的猜法会不会变如果允许一定概率猜错怎么设计策略另一个常见套路是“给你一个很大的有序数组但是你不知道它的长度是多少怎么找一个目标值”。这题的解法是先指数扩展边界找到right使得nums[right] target然后再普通二分。这个过程中指数查找的边界处理和后续二分的衔接都是考察点。6.2 二分答案在实际工程中的映射很多人觉得二分查找只存在于算法题里跟实际工作没多大关系。其实不然二分思想在工程里应用非常广泛。举一个例子线上服务需要限流你希望找到一个最优的QPS阈值使系统不被打垮的同时还能处理尽量多的请求。你可以把这看作一个在线二分问题先设一个阈值压测看系统是否稳定如果稳定就调高阈值如果不稳定就调低阈值通过多次迭代逼近最优值。再比如你有一个日志系统需要根据时间戳查询某条日志。日志是按时间存储的你写一个二分查找来定位时间戳比扫描全表快几个数量级。这些都是二分思想在实际问题中的应用。把这些讲给面试官听会明显比干巴巴说“我在LeetCode上刷过二分”要有说服力得多因为这证明你真正理解了二分背后的工程价值。6.3 面试时的沟通技巧面试中写二分查找我有几个个人体会值得分享。第一写完代码后主动说出复杂度。二分查找的时间复杂度是O(log n)但很多人会忽略空间复杂度。如果用的是递归写法空间复杂度是O(log n)用迭代写法空间复杂度是O(1)。说出这一点能让面试官觉得你基础扎实。第二主动测试边界条件。写完代码后不要急着说“完了”先在脑子里跑一遍空数组、单元素数组、目标在首尾、目标不存在这几种情况。这一步能避免大量边界bug也能展现你的工程素养。第三如果发现自己的代码有bug不要慌先在代码上用注释标出问题位置然后告诉面试官你的修复思路。面试官更看重的往往不是你一次写对而是你发现问题、修复问题的过程。7. 二分查找刷题路线与复盘模板最后分享一套我自己的二分专题刷题路线和复盘模板这也是我day73这个节点倒推回来的经验总结。7.1 推荐刷题顺序按难度递增我按从易到难的顺序整理了一个建议路线第一梯队搜索插入位置35、猜数字大小374、x的平方根69。这几道题帮你建立最基本的二分框架尤其是“搜索插入位置”一定要彻底吃透它是很多变体的基础。第二梯队爱吃香蕉的狒狒875、在排序数组中查找元素的第一个和最后一个位置34、寻找旋转排序数组中的最小值153。这个梯队的题开始涉及“二分答案”和“二分边界”这两个核心进阶点。第三梯队分割数组的最大值410、每个厨师做菜的最短时间2064、第k个缺失的正整数1539。这些题不仅考察二分的写法还考察验证函数的设计和贪心思维是真正拉开差距的题。第四梯队寻找两个正序数组的中位数4。这道题被评为hard是有道理的它对边界条件的要求极高也是面试中少数会直接考到hard题的场景。建议在前三梯队都刷完、对二分的边界处理有足够感觉之后再碰这道题。7.2 复盘模板一张表搞定每次刷完一道二分题我会在笔记里填一个简单的表格项目内容题目名称题目名编号二分对象数组下标 / 答案值域单调条件什么属性随搜索变量单调变化验证函数思路如何判断某个候选值是否可行边界条件left/right初始值、循环条件、指针更新规则踩过的坑这题最容易错的地方是什么相似题目可以归为一类的其他题目这个模板的好处是强制你思考每道题的本质而不是停留在“背代码”的层面上。坚持一段时间后你会发现很多看似不同的题目其实底层的二分对象和单调条件是一样的这时候你的解题速度会有一个质的飞跃。7.3 时间安排每天刷多少合适“面试经典150”一共150道题如果目标是三个月刷完平均每天1到2道加上周末复盘节奏是比较合理的。我自己倾向于工作日每天刷两道新题周末只做复盘和重刷错题不排新题。这样既能保持手感又不会因为连续刷题产生疲劳感。如果你发现有几天实在没时间也不用强求只要保证每周的总量达标就行。刷题是马拉松不是百米冲刺节奏比单日的爆发力更重要。8. 二分查找周赛题目的拓展思考最近几场周赛里也出现了不少二分查找的变体正好可以拿来检验自己对二分思想的理解深度。这些题目通常不是单纯的模板题而是把二分和其他算法技巧结合起来。8.1 二分加单调栈二维问题降维周赛里出现过一类涉及直方图最大矩形面积或二维矩阵的问题解法是在二分的基础上配合单调栈。这类题的关键是找到“可以二分的维度”然后在这个维度上套用单调栈来验证。比如给你一个二维矩阵找出最大的全1正方形边长。这题除了动态规划解法外也可以对边长进行二分然后用前缀和或滑动窗口验证是否存在边长为mid的全1正方形。思路的本质是把“是否存在满足条件的解”转成一个可验证的问题然后二分这个边长。这类题看起来吓人但只要突破了“二分对象”这一层思维代码反而非常简洁。8.2 二分加差分数组区间问题的优化另一类高频题是“给定一个数组多次修改区间值求最终数组”或“求满足某个区间条件的最优方案”。这类题里二分答案配合差分数组是很经典的组合。思路是这样的二分最终的答案x然后用差分数组模拟区间操作检查是否存在一个区间内的值不满足条件从而判断x是否可行。差分数组让区间修改变成O(1)操作整体复杂度可以做到O((n m) * log(maxVal))比直接模拟快得多。8.3 从周赛题目回归面试经典周赛的题目往往比面试经典150更难但它们的解题思路基本都能在经典题里找到原型。比如周赛里“最大化城市的最小供电量”这类题本质上就是“分割数组最大值”的变形只不过把“数组分段”换成了“城市供电覆盖”。所以我的建议是先把面试经典150里的二分题吃透再去挑战周赛的变体题。反过来如果你周赛的二分题能做出来面试中遇到经典二分题基本不会卡壳。两条路线互相验证是检验掌握程度的很好方式。9. 二分查找的常见问题速查表在日常答疑和讨论群里我发现大家问得最多的问题高度集中这里整理成一个速查表方便你随时查阅。问题原因分析解决办法死循环left和right差1时left mid配合向下取整改用向上取整或统一左闭右开模板结果差1边界条件没处理好返回left还是right分不清在纸上推演2-3轮验证返回值位置初始区间把答案排除了没想清楚答案的上下界先确定答案的最小可能值和最大可能值验证函数超时验证函数内部写成了O(n^2)优化为O(n)扫描必要时用前缀和或差分数组找不到答案target不存在或right边界设置过小先检查初始区间再检查边界返回值二分查找和索引混淆分不清是对下标二分还是对答案值域二分先判断是否“找到某个元素”再考虑答案值域这张表格是我从自己的刷题记录里提炼出来的基本上囊括了二分查找八成的踩坑场景。如果你刷题时遇到问题可以先对着这张表排查一圈大概率能快速定位。10. 写在最后刷题笔记的个人习惯最后分享一个个人习惯。我刷题时会准备两份笔记一份是“刷题日历”记录每天刷了哪些题、耗时多少、正确率如何另一份是“专题总结”按专题记录核心思路、变体、易错点。两种笔记互相配合日历负责维持节奏总结负责沉淀知识。day73这个节点上我回头看二分专题的总结已经积累了不少内容。如果让我只保留一条最核心的经验那就是二分查找的框架代码背熟只是基本功真正拉开差距的是你能不能准确判断“二分的对象是什么”和“验证函数怎么写”。这两个问题想通了二分专题基本就拿下了一大半。接下来按“面试经典150”的进度二分专题还剩几道进阶题刷完之后就会进入排序和链表专题。希望这篇二分经验帖对正在刷题的你有帮助也欢迎交流各自的刷题心得。