刷完面试经典150二分专题：边界条件与二分答案核心总结

从三个月前决定认真刷题开始，我给自己定的目标是每天至少两道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。

这个题的暴力解法是从K=1开始逐个尝试，最小的满足吃完时间 <= 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根，K=3，那么这一堆需要4小时（3+3+3+1），用这个公式算出来就是(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 复盘模板：一张表搞定

每次刷完一道二分题，我会在笔记里填一个简单的表格：

这个模板的好处是强制你思考每道题的本质，而不是停留在“背代码”的层面上。坚持一段时间后，你会发现很多看似不同的题目，其实底层的二分对象和单调条件是一样的，这时候你的解题速度会有一个质的飞跃。

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. 二分查找的常见问题速查表

在日常答疑和讨论群里，我发现大家问得最多的问题高度集中，这里整理成一个速查表，方便你随时查阅。

这张表格是我从自己的刷题记录里提炼出来的，基本上囊括了二分查找八成的踩坑场景。如果你刷题时遇到问题，可以先对着这张表排查一圈，大概率能快速定位。

10. 写在最后：刷题笔记的个人习惯

最后分享一个个人习惯。我刷题时会准备两份笔记，一份是“刷题日历”，记录每天刷了哪些题、耗时多少、正确率如何；另一份是“专题总结”，按专题记录核心思路、变体、易错点。两种笔记互相配合，日历负责维持节奏，总结负责沉淀知识。

day73这个节点上，我回头看二分专题的总结，已经积累了不少内容。如果让我只保留一条最核心的经验，那就是：二分查找的框架代码背熟只是基本功，真正拉开差距的是你能不能准确判断“二分的对象是什么”和“验证函数怎么写”。这两个问题想通了，二分专题基本就拿下了一大半。

接下来按“面试经典150”的进度，二分专题还剩几道进阶题，刷完之后就会进入排序和链表专题。希望这篇二分经验帖对正在刷题的你有帮助，也欢迎交流各自的刷题心得。