集训进行到第17天终于轮到二分查找了。说它“终于”是因为数组、链表、栈、队列这些基础结构排着队过了一遍之后同学们第一次接触到真正意义上的“非暴力”算法就是二分查找。二分查找算法本身不难三五行代码就能写完但真正把它写对、写稳理解它为什么快、能用在哪却是很多人的分水岭。这篇内容我按基础算法集训第17天的进度来写围绕二分查找算法从原理讲到实战再把 LeetCode 必刷基础算法题和 PTA 函数题里常见的坑一起捋一遍。适合正在刷题的学生、准备面试的开发者以及所有想把二分查找模板彻底吃透的人。1. 二分查找的本质为什么它能省掉这么多时间1.1 有序数据的“排除法”思维先问一个问题如果让你在一本按拼音排序的厚字典里找一个字你会怎么做正常人不会从第一页开始逐页翻而是会先翻到中间看看目标字在前半本还是后半本然后不断把范围缩小直到翻到那一页。二分查找干的就是这件事只不过把“翻字典”变成了“查数组”把“指尖的快感”变成了“程序的效率”。算法的流程非常简单维护两个指针 left 和 right分别指向当前搜索区间的左右端点。每次取中间位置 mid比较 mid 位置的值和目标值 target 的大小关系。如果相等直接返回如果中间值小于 target说明目标只可能在右半区间让 left mid 1如果中间值大于 target说明目标只可能在左半区间让 right mid - 1。如此循环区间长度会以指数速度收缩。为什么能用“排除法”前提是数组有序。在有序数组中比较结果可以告诉你目标的大致方位一次比较斩杀掉一半的不可能区域。这就是二分查找的核心收益每一轮迭代后剩余搜索空间减半。这个思路看起来平平无奇但它是很多高效算法的基础也是“二分答案”这类进阶技巧的起点。1.2 时间复杂度与“猜数字”直觉二分查找的时间复杂度是 O(log n)这个 log 以 2 为底。很多人对这个复杂度没有直观感觉我给你一组数据处理 100 万个有序元素顺序查找最坏要比较 100 万次二分查找最多只需要比较 20 次。100 万和 20 的差别就是暴力解和高效率解的分界线。从“猜数字”游戏也能获得同样的直觉一个人在 1 到 100 之间想一个数另一个人每次猜完只得到“大了”或“小了”的反馈。最优策略下最多 7 次一定猜中因为 2 的 7 次方是 128正好覆盖 100 个数字。如果你从 1 开始一个一个猜运气差时得猜 100 次。这里的差值就是信息利用率的差值。要强调一点二分查找不是万能的。它要求数据结构支持随机访问也就是能在 O(1) 时间内拿到中间位置的元素。数组满足这个条件而链表不满足。链表的“二分”需要先遍历到中间位置每次迭代都要 O(n)整体复杂度退化到 O(n log n)还不如直接顺序查找。所以看到链表先别想着套二分模板。2. 三种边界写法彻底搞定二分模板2.1 模板一左闭右闭区间写法最经典的写法是“左闭右闭”区间即 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因为区间是闭区间当 left 和 right 相等时区间里还有一个元素不能提前退出。每次比较后更新指针时由于 nums[mid] 已经被检查过下次搜索区间必须把它排除掉所以 left 更新为 mid 1right 更新为 mid - 1。模拟一个简单例子nums [1, 3, 5, 7, 9]target 7。第一轮 left 0right 4mid 2nums[2] 5 7说明目标在右半侧left 变为 3。第二轮 left 3right 4mid 3nums[3] 7命中。整个过程只比较了两次非常有效率。2.2 模板二左闭右开区间写法另一种常见写法是“左闭右开”区间即 left 在区间内right 在区间外。C 的 STL 里大量使用这种区间约定比如 iterator 的 begin 和 end 就是这种关系。代码如下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注意两个关键区别初始 right len(nums) 而非 len(nums) - 1循环条件是 left right 而非 left rightright 更新为 mid 而非 mid - 1。因为 right 本身指向的是一个“不检查”的位置所以把 mid 赋给 right等价于把区间收缩到左半部分同时把 mid 排除在外。这个写法理解起来比左闭右闭稍抽象但它有一个好处配合“找左边界”“找右边界”这类变体问题时语义更清晰。我自己的经验是如果你刚开始学先用左闭右闭模板练熟一套等刷到二分进阶题再慢慢体会左闭右开的优雅之处。2.3 模板选型心得与 mid 计算防溢出先回答一个新手常问的问题两个模板到底选哪个我的建议是选定一个作为“主场”另一个至少要能看懂。左闭右闭模板更符合人类直觉适合快速手写左闭右开模板在 C 的 lower_bound、upper_bound 等库函数中存在感极强遇到 STL 相关代码时你必须有阅读能力。再聊一个隐藏很深的坑mid 的计算。很多人直接写 (left right) // 2这在 Python 里没问题因为整数不会溢出。但在 C 或 Java 里当 left 和 right 都接近整数上限时left right 可能溢出导致 mid 变成负数程序直接出错。稳妥的写法是 left (right - left) // 2也就是先算区间长度再取一半。这个写法在任何语言里都安全。我在集训里反复强调一句话写二分先把区间定义写在注释里。左闭右闭还是左闭右开写清楚了循环条件和指针更新就不容易错。3. 从 LeetCode 到 PTA经典题目手把手拆解3.1 LeetCode 704最简单的二分查找LeetCode 704 是二分查找的“入门必做题”题目就是在一个升序数组里找 target找到返回下标找不到返回 -1。这题没什么花样直接套模板即可。class Solution: def search(self, nums: List[int], target: int) - int: 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把这题当作“基准题”来刷意义在于建立一个标准动作确认有序性、确定区间定义、写出循环、验证边界。我见过太多人一上来就写 while left right然后在返回时补一堆特判最后把自己绕晕。记住704 这种题就该用最朴素的左闭右闭写法不需要任何花活。3.2 LeetCode 35搜索插入位置LeetCode 35 是 704 的进阶版数组里可能没有 target要求返回它应该被插入的位置让数组依然有序。举个例子nums [1, 3, 5, 6]target 5 返回 2target 2 返回 1target 7 返回 4target 0 返回 0。这题表面上是一个新问题但换个视角就变成了找到第一个“不小于 target”的位置。只要用二分找下界就完美解决。模板如下class Solution: def searchInsert(self, nums: List[int], target: int) - int: left, right 0, len(nums) - 1 ans len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: ans mid right mid - 1 else: left mid 1 return ans注意这里我引入了一个 ans 变量来记录“目前见到的第一个不小于 target 的位置”。初始值设为 len(nums) 是为了处理 target 比所有元素都大的情况此时 ans 不会被更新最终返回的就是数组长度含义是插入到末尾。这个“记录答案”的技巧非常重要。搜索插入位置、找左边界、找右边界本质上都是“在按某种条件划分的数组里找分界点”用一个 ans 变量把候选答案带出来比在循环结束后靠 left 或 right 的取值去反推答案要稳得多。3.3 LeetCode 34查找元素的第一个和最后一个位置LeetCode 34 是二分查找里的“分水岭”题目给定一个有序数组其中可能包含重复元素要求返回 target 的第一个位置和最后一个位置不存在则返回 [-1, -1]。例子nums [5, 7, 7, 8, 8, 10]target 8返回 [3, 4]。这题的关键是不能用一次二分找到任意一个 target 就收工因为重复元素的存在让“任意一个位置”无法确定左右边界。正确做法是写两个二分函数一个找第一个不小于 target 的位置一个找第一个大于 target 的位置再减一。class Solution: def searchRange(self, nums: List[int], target: int) - List[int]: def lower_bound(): left, right 0, len(nums) - 1 ans -1 while left right: mid left (right - left) // 2 if nums[mid] target: ans mid right mid - 1 else: left mid 1 return ans if ans ! -1 and nums[ans] target else -1 def upper_bound(): left, right 0, len(nums) - 1 ans -1 while left right: mid left (right - left) // 2 if nums[mid] target: ans mid left mid 1 else: right mid - 1 return ans if ans ! -1 and nums[ans] target else -1 return [lower_bound(), upper_bound()]lower_bound 找第一个不小于 target 的位置upper_bound 找最后一个不大于 target 的位置。找到后都要再检查一下 nums[ans] 是否真的等于 target否则说明 target 不存在。这个套路在 C 里就是 lower_bound 和 upper_bound 的配合非常经典。刷这题容易犯的错是找到第一次出现的 target 后立刻向左右线性扩散。比如 704 找到 8 之后用 while 往两边找同值元素。这种写法在数组全是 8 的时候一次扩散就是 O(n)完全失去了二分的意义。面试官看到这种写法印象分会大打折扣。3.4 PTA 函数题二分查找怎么过PTA 上的“二分查找”函数题是很多学校数据结构课的经典作业。题目通常会给你一个已按升序排列的顺序表要求在表里查找给定关键字找到返回位置找不到返回 NotFound。下面是一份典型的 C 语言解法Position BinarySearch(List L, ElementType X) { Position left 1, right L-Last; while (left right) { Position mid left (right - left) / 2; if (L-Data[mid] X) return mid; else if (L-Data[mid] X) left mid 1; else right mid - 1; } return NotFound; }这里有几个容易踩的坑。第一PTA 的顺序表存储结构通常定义数据从下标 1 开始所以 left 要从 1 开始right 用 L-Last 而不是 L-Last - 1。第二NotFound 在题目里一般被宏定义成 0因为有效位置从 1 开始0 可以被用作“找不到”的标志。第三mid 的写法我用的是 left (right - left) / 2在 C 语言里同样为了防止 left right 的整数溢出。很多同学做这道题时死在“下标从 0 还是从 1 开始”这个问题上。做题之前先看清题目给的 List 结构定义确认数据存储起点这是比背模板更重要的一步。PTA 的隐藏用例最喜欢考验你对定义细节的理解区间初始化错了样例过了也照样扣分。4. 二分答案当“查找”变成“判定”4.1 单调函数与答案二分的思想集训到第 17 天二分查找还有一个更高级的玩法二分答案。它的核心思想是不再直接在数组里找 target而是把问题抽象成一个单调的判定函数 f(x)然后对 x 的取值范围进行二分找到满足条件的最优 x。举个例子假设要求在某种条件下“最小化最大值”或者“最大化最小值”这类问题如果直接构造答案会很困难但给定一个候选答案 x你却能快速判断这个 x 是否可行。单调性保证如果 x 可行那么所有大于 x 的值也可行如果 x 不可行所有小于 x 的值也不可行。于是整个值域变成了一个巨大的“有序数组”一群“可行”的 x 排在前面或后面二分查找就能在这个值域上找到那个临界点。生活化一点你调节水温试到某个温度觉得烫往下调一度就不烫了。温度是连续变化的舒适/不舒适的状态只有一个分界点这个分界点就能用二分法快速逼近。找水温不需要一格一格去试二分答案也是在“捡效率”。4.2 经典实战爱吃香蕉的珂珂LeetCode 875 是一道非常标准的二分答案题。珂珂要在 h 小时内吃掉 n 堆香蕉每堆有 piles[i] 根她只能选择某个速度 k根/小时求能按时吃完的最小 k。这里的约束是同一堆香蕉在一个小时内只能吃 k 根不能从一堆中途跳到另一堆所以每堆耗时是 ceil(piles[i] / k)。这个问题的特点是速度 k 越大总耗时越小单调性非常明显。我们可以写一个判定函数 can_finish(k)计算按速度 k 吃完所有香蕉需要多少小时判断是否不超过 h。然后对 k 从 1 到 max(piles) 进行二分找最小的可行值。class Solution: def minEatingSpeed(self, piles: List[int], h: int) - int: def can_finish(k): return sum((p k - 1) // k for p in piles) h left, right 1, max(piles) while left right: mid left (right - left) // 2 if can_finish(mid): right mid - 1 else: left mid 1 return left注意这里的 left 初始值是 1而不是 0因为吃香蕉速度必须为正整数right 初始值是 max(piles)因为速度超过最大堆的量没有意义耗时不会更少。循环结束后的 left 就是满足条件的最小速度配合“记录 ans”的思想也完全一致。这类题刷多了你会发现二分答案的难点从来不在模板而在能不能看出来“答案具有单调性”。我集训时经常提醒同学们看到“最小化最大值”“最大化最小值”以及“求某个满足条件的临界值”这类字眼优先想想能不能变成二分答案。4.3 浮点数二分的注意事项二分答案并不局限于整数。求平方根、求方程零点、求浮点数范围内的最优解都可能用到浮点二分。浮点二分和整数二分最大的区别有两个循环条件和停止标准。浮点数无法精确判断相等通常不用 while (left right)而是用“迭代固定次数”或者“区间长度小于某个极小值 eps”来终止。经验值上如果要求保留 6 位小数eps 可以取 1e-8保留 4 位eps 取 1e-6 即可。不过我更推荐固定迭代次数比如循环 100 次因为 100 次二分能把区间长度缩到初始长度的 2 的 -100 次方已经完全超过绝大多数题目的精度要求还能避免 eps 设置不当导致的死循环。def sqrt_binary(x): if x 0: return None left, right 0, max(1.0, x) for _ in range(100): mid (left right) / 2 if mid * mid x: left mid else: right mid return left这个例子里我把 left 初始化为 0right 初始化为 max(1.0, x)是为了处理 x 小于 1 的情况。比如求 0.25 的平方根答案是 0.5而 0.5 大于 0.25所以 right 不能简单设为 x否则就搜不到正确值。浮点数二分的初始化边界是另一个新手重灾区。5. 集训17天最常见的坑问题排查速查5.1 死循环的根源与调试方法二分查找写崩最常见的就是死循环。一个典型的错误写法while left right: mid (left right) // 2 if mid target: left mid else: right mid - 1这个例子里当 mid 计算出来等于 left 时如果条件满足left mid 没有让区间缩小循环就卡死了。死循环的根源本质上是“区间更新没有严格缩小搜索范围”。遇到死循环不要慌用最笨的方法排查拿一个长度 2 或 3 的小数组手动模拟每一轮迭代把 left、right、mid 三个值的变化写下来。通常跑两三轮就能看出问题出在哪一步。更高效的做法是在代码里临时加打印把每轮的值打出来跑一遍立刻暴露问题。等代码稳定后再把调试信息删掉。5.2 边界更新的黄金法则我总结了一条规则基本能规避绝大多数二分问题下一轮的搜索区间必须严格小于当前区间并且已经比较过的 mid 必须从新区间中排除。按照这条规则当你写 mid left (right - left) // 2 且取的是下取整时如果分支是 left mid那么新区间可能没有收缩要让区间严格收缩取中偏左时left 必须更新为 mid 1如果某分支确实需要 left midm 就要用“取中偏右”的计算比如 mid left (right - left 1) // 2。更朴素的做法是优先使用“排除 mid”的标准写法即 left mid 1 和 right mid - 1。只有在左闭右开模板或二分答案中才需要右边界更新为 mid。等你能清楚地讲出“当前区间还剩哪些元素”的时候边界问题基本就不再困扰你了。5.3 二分查找常见问题速查表现象可能原因解决办法死循环left mid 时取中偏左区间未收缩改为 left mid 1或改用取中偏右返回错误下标区间定义不清晰初始化 right 多 1 或少 1先写注释明确闭区间还是开区间找左边界却返回右边界等号处理错误条件写成 nums[mid] target用“第一个不小于 target”的判定条件有重复元素时结果不稳找到任意 target 就返回改用 lower_bound / upper_bound 模板C/Java 中 mid 变负数left right 整数溢出用 left (right - left) // 2浮点二分不收敛eps 设置过粗或过严固定迭代 100 次或用更小 eps二分答案初始边界错left 或 right 未覆盖可行解仔细推值域范围比如速度从 1 开始这张表基本覆盖了我集训 17 天以来学生们遇到的大部分问题。最后再补充一个刷题建议LeetCode 上的必刷基础算法题中与二分查找相关的至少有 704、35、34、69、875 这几道建议按这个顺序刷。704 练标准模板35 练“找下界”思想34 练左右边界变体69 练浮点二分875 练二分答案。把这五道题刷透基础算法集训中二分查找这一关就算真正过了。我个人教学中最深的体会是二分查找的难度不在“会写模板”而在“遇到新题时能不能识别出单调性”。集训第 17 天的学生很多人看完模板能立刻 AC 704但遇到 875 就卡住了。区别就在于有没有建立“值域二分”的视角。所以如果你目前卡在某一类二分题上不妨停下来想一想这个题目里哪个量的变化是单调的把它当成二分搜索的对象思路可能一下子就通了。这个小技巧我每次带集训都会反复叮嘱。