二分查找与二分答案：从LeetCode 073到周赛430的实战蜕变-北京尧图网络

1. 第28届打卡Day04我为什么在这个节点开始死磕二分查找1.1 28届LeetCode活动的前三天我经历了什么跟完第28届LeetCode刷题打卡活动前三天基本处在一种感觉会了又感觉什么都不会的飘忽状态。Day01和Day02集中刷数组、哈希表、双指针这类基础专题题目难度以简单到中等为主每天两三道跟着题单走倒也顺畅。Day03开始上强度出现了滑动窗口和前缀和的组合题我第一次在草稿纸上画了半天窗口收缩的逻辑才勉强把代码调通。到了Day04题单突然拐进了一个我很熟悉、但从来没真正搞懂过的领域二分查找。我当时的心理活动是二分查找不就是while left right嘛有什么好学的结果当天第一道题073爱吃香蕉的狒狒就把我按在地上摩擦了一上午。这道题在活动题单里编号073对应LeetCode原题875 Koko Eating Bananas是一道典型的二分答案入门题。我一开始甚至没意识到它和在有序数组里找某个数这种经典二分有什么区别直到被超时教育了才老老实实去研究。1.2 今天的刷题路线073 热门100题周赛430Day04的完整安排是这样的白天啃完073爱吃香蕉的狒狒又从LeetCode热门100题里挑了33搜索旋转排序数组和34在排序数组中查找元素的第一个和最后一个位置做横向对比晚上参加周赛430当实战检验。这条路线是活动官方推荐的节奏先通过一道经典题理解核心思想再用同类型热门题巩固最后用周赛检验真实掌握程度。回头看这条路线最大的价值不是让我多刷了几道题而是让我第一次把二分查找从会写模板升级到了知道为什么这么写。很多人在LeetCode上刷了几百题遇到二分题还要现推一遍边界条件就是因为缺少这一层理解。我今天想把这天的完整思考过程写下来尤其是073这道题的推导、热门100题里二分变体的横向对比、以及周赛430暴露出的真实问题给同样在打卡的朋友一个可以直接参考的路径。1.3 前置概念二分查找和二分答案根本不是一回事在进入073之前必须先搞清楚两个概念二分查找Binary Search和二分答案Binary Search on Answer。我们在教科书里学的经典二分查找对象是一个有序数组目标是在数组里找到某个特定值的下标。比如在[1, 3, 5, 7, 9]里找7每次比较中间值缩小搜索范围复杂度O(log n)。这类题的核心特征是数据本身有序我们二分的是下标。而二分答案的对象不是数组是解的空间。目标是找到满足某个条件的最小值或最大值。比如073这道题我们要在所有可能的吃香蕉速度k里找最小的那个k。这里的k不是一个数组元素而是一个数值区间我们能对它二分是因为存在一个单调性k越大吃完所有香蕉所需的总时间越短。只要这个单调性成立我们就可以把找最小可行解变成一个二分问题。这个区别是今天所有内容的地基。后面对比热门100题里的33、34时你会发现它们有的是二分下标有的是二分答案但底层的利用单调性缩小搜索区间逻辑是完全一致的。2. 073爱吃香蕉的狒狒从暴力超时到二分答案的完整推导2.1 题目到底在说什么以及我最开始的天真想法题意其实非常生活化狒狒面前有n堆香蕉第i堆有piles[i]根。它需要在h小时内全部吃完但每小时只能选择一堆并且这一小时里最多吃k根。如果某一堆剩下的香蕉不足k根狒狒就把它全部吃完但这一个小时也不能再去吃别的堆。现在要找一个最小的速度k使得狒狒能按时吃完。我第一次看到这道题脑子里立刻蹦出来的思路是从k1开始枚举每个k都模拟一遍狒狒吃香蕉的过程第一个能让总时间不超过h的k就是答案。这样想非常自然但问题也很明显k的最大值可能达到piles数组的最大值比如piles[i]10^9那k的范围就有10^9这么大每个k都要遍历一遍所有堆总复杂度O(max(piles) * n)直接超时到天际。LeetCode官网给的题目约束里piles长度最大是10^4每堆香蕉最多10^9根。这个数据规模下枚举法根本不可能跑完。看完约束条件我就知道必须换思路。2.2 把找最小速度变成判断某个速度行不行卡了十分钟后我意识到虽然不能枚举每个k但可以观察到这样一个性质给定一个速度k我们能不能在h小时内吃完这件事是容易算的。对于每一堆piles[i]以速度k去吃需要的时间是ceil(piles[i] / k)小时向上取整把所有堆的时间加起来就是总时间T(k)。只要T(k) h说明k是可行的。于是问题变成了在所有可行的k里面找最小的那个。而T(k)有一个天然的性质——k越大每堆消耗的小时数越少T(k)就越小。也就是说T(k)关于k是单调递减的。单调递减意味着什么它意味着可行集不是零零散散的而是一段连续的区间从某个值开始所有更大的k都可行小于这个值的k都不可行。这个临界值正是我们要找的答案。既然可行解在数轴上满足单调性我们就可以用二分去逼近这个临界值。这就是二分答案的本质不直接求答案而是反复猜测一个答案验证它行不行然后根据验证结果缩小猜测范围。这类题的固定套路是写一个check函数入参是猜测值k返回这个k是否可行然后在解空间里用二分框架不断调用check最终锁定临界值。check函数负责把求解题变成判断题二分框架负责高效地找到那个判断结果为true的最小值。2.3 check函数怎么写向上取整的细节是第一个坑073的check函数非常直观def can_finish(k, piles, h): total_hours 0 for p in piles: # 每堆需要 ceil(p / k) 小时 total_hours (p k - 1) // k return total_hours h这里最容易出错的是向上取整的写法。如果用浮点数除法再ceil比如math.ceil(p / k)在p和k都很大、且是整数除法时有精度隐患。更稳妥的做法是使用整数运算技巧(p k - 1) // k。原因是p除以k向上取整等价于求最小的整数q使得q*k p而(p k - 1) // k正好满足。我一开始写成p // k 1看着差不多实际错误百出。比如p5, k3正确结果是2但5 // 3 1 2是对的再比如p6, k3正确结果是26 // 3 1 3就错了。因为当p恰好是k的整数倍时不需要额外加1。(p k - 1) // k这个写法天然涵盖了整除和有余数两种情况有余数时加k-1让商多进一位无余数时又刚好不进位非常巧妙。2.4 二分边界的设计left取1right取max(piles)check函数解决之后接下来就是二分框架的边界问题。很多人在二分题上卡最久的就是左右边界和循环不变式的选择。073这道题的解空间是速度k范围从多少到多少left下界可以取1因为速度最小就是每小时1根再小没有任何意义。right上界取max(piles)因为如果速度等于最大堆的根数狒狒每小时最多吃光一堆已经是每堆只花1小时的极限速度了。速度再大也不可能把时间压到少于堆数n小时。所以最小可行速度一定不会大于max(piles)。在区间[left, right]上使用常见的左闭右闭二分模板def minEatingSpeed(piles, h): left, right 1, max(piles) while left right: mid (left right) // 2 if can_finish(mid, piles, h): right mid # mid可行尝试更小的速度 else: left mid 1 # mid不可行只能加大速度 return left这套模板的循环不变式是答案始终落在[left, right]之间。当check(mid)为true说明mid及比mid大的方向都可行但我们要找最小可行值所以把右边界收缩到mid当check(mid)为false说明mid太小了连mid都不可行那比mid小的更不可行所以左边界收缩到mid1。循环结束时left就是最小可行速度。使用while left right而不是while left right配合上面的收缩方式可以避免死循环和越界这也是目前LeetCode社区最主流的闭区间写法。2.5 完整代码与复杂度把上面的check和二分组合起来完整实现如下class Solution: def minEatingSpeed(self, piles: List[int], h: int) - int: def can_finish(k): total 0 for p in piles: total (p k - 1) // k return total h left, right 1, max(piles) while left right: mid (left right) // 2 if can_finish(mid): right mid else: left mid 1 return left时间复杂度二分次数是O(log(max(piles)))每次check要遍历整个piles数组所以总复杂度O(n * log(max(piles)))n是堆数。空间复杂度只用了几个常量变量O(1)。提交之后看到绿色的Accepted我长舒一口气。但随后我意识到一个更关键的问题这道题我虽然写对了但如果题目稍微变一变比如把每小时最多吃k根改成每堆必须按顺序吃我还能不能反应过来带着这个问题我转向了热门100题里的二分题。3. 一题懂一类热门100题里的二分变体怎么横向迁移3.1 今天选的两道对比题33和34073刷完之后我没有急着看下一道新题而是从LeetCode热门100题里挑了两道二分相关题目做对比33. 搜索旋转排序数组以及34. 在排序数组中查找元素的第一个和最后一个位置。这两道题非常经典都在热门100题里有固定位置。选择它们的原因很简单34和073一样本质是二分边界33则引入了分段有序的概念考验对单调性的理解是不是真的透彻。先看34。题目要求在一个升序排列的整数数组里找出目标值的第一次出现位置和最后一次出现位置。很多人第一反应是先用一次二分找到任意一个目标值再向两边线性扫描但在极端情况下比如整个数组都是同一个值线性扫描会退化成O(n)不符合二分题的要求。正确做法是把找左边界和找右边界分别用一次二分解决。找左边界时我们可以这样理解二分对象是下标但判断条件是nums[mid] target。当这个条件成立时说明mid位置的值不小于目标那mid以及它右边都不可能是第一个小于target的位置所以收缩右边界当条件不成立时说明mid位置小于target左边界要右移。最终left指向的位置就是第一个 target的位置。3.2 三道题的二分对象和单调性来源为了让横向对比更直观我把073、33、34放在一张表里看题目二分对象单调性来源核心判断逻辑073 爱吃香蕉的狒狒速度k数值区间速度越大总用时越短sum(ceil(p/k)) h34 查找元素范围数组下标数组本身升序nums[mid] target33 搜索旋转排序数组数组下标分段有序先判断哪一半有序再决定搜索方向这张表很直观地揭示了一个规律无论二分对象是数值还是下标都依赖一个重要的前提——存在某种单调性。073的单调性来自吃香蕉的总时间随速度递减34的单调性来自升序数组本身33则稍微特殊一点旋转数组整体不是单调的但任何一刀切下去左右两半中至少有一半是完整有序的。这个至少一半有序的性质就是旋转数组可以二分的依据。3.3 从073到33的思维迁移先判断单调性再写代码具体到33题代码框架并不复杂def search(nums, target): left, right 0, len(nums) - 1 while left right: mid (left right) // 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]如果有序再判断target是否落在这个有序区间内如果不是左半段有序那右半段必然有序做对应的判断。这个模式不靠背靠的是理解旋转后数组被分成两个有序段mid永远把数组切成一个完全有序段和另一个可能有序也可能无序的段而我们只在那一个完全有序段里做范围判断。学完33和34我再回头看073发现它们都在做同一件事找到单调性的分界点。只不过073的边界是速度34的边界是相同元素的首尾位置33的边界是旋转点。所以我把073、33、34归成一组在笔记里写了一句二分题的本质不是while循环而是先回答两个问题——你的搜索空间是什么这个空间里存在什么单调性4. 周赛430复盘一次真实比赛暴露出的三个致命问题4.1 赛前状态和我的策略晚上八点的周赛430是今天的重头戏。说实话Day04就参加周赛我心里是有点虚的。前三天虽然刷了十几道题但竞赛和刷题完全是两种生物竞赛要在有限时间内读题、建模、调试、提交任何环节卡壳都会直接掉分。我的策略是前两道题控制在15分钟内第三道题允许20分钟超过时间果断放弃去做第四道的骗分输出。赛前我以为这个策略很合理结果现实给了我一巴掌。4.2 我在T2上的恋战把简单问题想复杂的典型失误周赛430的第一题很快就过了属于签到题没有太多讨论价值。问题出在第二题。我读完题面之后第一反应是这题应该双指针于是吭哧吭哧写了十几分钟的滑动窗口代码样例过了一提交就是WA。我开始慌了又回去重读题才发现这题的条件非常直接本质上就是一个区间上求满足约束的最小范围用双指针勉强能做但正确姿势其实是二分答案——对答案区间做二分每次都判断当前窗口是否可行。这个失误很典型它不是不会做而是在没完全理解题意之前就急着套模板。如果我用和白天073一样的方法论先问自己搜索空间是什么单调性是什么那么很快就能发现这题的可行窗口大小具有单调性——窗口越大越容易满足条件于是直接二分窗口长度就行。但我偏偏因为竞赛中第一题做完带来的兴奋感跳过了这一步选择了双指针硬刚白白浪费了二十分钟。4.3 时间管理的代价和竞赛与日常刷题的差距T2卡了太久的直接后果是T3只剩不到十分钟。读到T3题目时我一眼就认出这是一道二分答案题——和073一个套路check函数也不难写。但在那种高压状态下我的大脑根本没法冷静组织代码手一抖把边界条件写错了直到比赛结束都没调出来。最终成绩自然惨淡但这场周赛让我用最真实的方式检验了白天学的二分查找。赛后我认真复盘得出三个结论第一竞赛中时间是最稀缺的资源不该恋战的地方绝不能恋战。一道题卡了10分钟没有思路就应该立刻转移留在最后哪怕暴力也能骗一点分至少比浪费光所有时间强。第二模板必须形成肌肉记忆。白天073那种while left right加上if check(mid): right mid else: left mid 1的闭区间二分我在日常刷题时可以慢慢推导但在周赛里根本没有推导时间。平时把边界模板练到闭着眼睛能写竞赛才能空出脑容量去思考题目本身。第三读题比做题重要。我在T2上最大的错误不是算法不会而是题目理解偏了。吃一堑长一智之后我要求自己读题至少读两遍第一遍只看不写第二遍边读边在纸上标出所有约束条件确认之后才开始想算法。5. Day04沉淀题解阅读三步法、二分模板和四天心态变化5.1 我的题解阅读三步法白天刷完073和热门100题晚上参加完周赛这一天还剩下最后一项任务看题解、写复盘。说来好笑前三天刷题我都是不会做 - 直接看题解 - 抄一遍 - 下一题结果晚上复盘发现什么也没记住。Day04我特意改变策略把题解阅读分成三步第一步先独立思考至少20分钟。实在想不出来才允许打开题解区。这个20分钟不是随便定的而是来自注意力研究里的一个概念人在一个问题上连续思考20分钟后大脑会把相关信息在后台重组即使你暂时没想出来稍后看到题解时也更容易理解关键思路。我在073上就试了卡了15分钟虽然没有完全想出二分答案的写法但已经隐约意识到总时间随k有单调性这时候再看题解一眼就懂了。如果一开始就看题解就永远不会有这一层隐约的认知。第二步看题解时只看思路不看代码。我会先把题解里的核心思想用自己的话说一遍比如073的核心是速度越大耗时越短所以可以二分速度。把这个核心句子写在笔记本上然后再回过来自己写代码。一旦依赖题解代码很容易出现看着会了合上就忘的情况。第三步对比自己和题解的差异。写完之后再回看题解重点不是看谁的代码短而是看边界条件和判断逻辑的不同。073我最初写的是while left right配mid (left right) // 2后来看官方题解和热门题解都是while left right配左闭右闭区间收缩两者都能过但后者在找最小可行值这种场景下更不容易出现死循环。这种差异就是值得记下来的经验。5.2 关于二分查找我总结的通用模板和记忆口诀经过Day04一天的折腾我整理了一套二分查找的通用模板适用于大部分二分答案题也适用于34题这种边界题# 在 [left, right] 区间内寻找第一个满足 check 条件的位置 left, right 初始下界, 初始上界 while left right: mid (left right) // 2 if check(mid): right mid # mid 可行答案在左边包含 mid else: left mid 1 # mid 不可行答案在右边 return left这套模板的记忆口诀是可行收缩右边界不可行左边界加一循环到左右相遇。使用它的前提是check函数具有单调性要么随着mid增大从false变true要么从true变false如果二分目标是最小可行值就套这个模板如果找最大值只要把check条件取反或者调整收缩方向即可。对于34题的左右边界我会额外记找第一个位置用nums[mid] target作为check条件找最后一个位置用nums[mid] target作为check条件分别套模板。因为本质都是第一个满足某条件的位置。5.3 连续打卡四天我真实的心态变化最后说说心态。Day01的时候我充满了三分钟热度一天刷了六道题感觉自己天下无敌。Day02开始遇挫一道中等题卡了两个小时晚上差点放弃。Day03靠题解勉强跟上了进度但心里发虚。到了Day04我反而平静了。不是因为题目变简单了而是我开始接受一个事实刷题本来就是反复卡壳、反复看题解、反复遗忘又反复捡起来的过程。073这道题让我明白了一道题学透比做十道题有用这句话不是鸡汤。通过一道题吃透二分答案然后横向对比热门100题里的33和34最后在周赛430里被真实比赛狠狠教育一波这一天的完整闭环让我知道刷题的核心不是数量而是每道题都在脑子里留下结构化的认知哪怕是错误也要明明白白知道错在哪。如果你也在跟第28届LeetCode打卡活动或者正处在某个刷题计划的初期我的建议是不要怕慢。Day04花了一整天只完整掌握二分查找这一个考点看上去效率很低但这套基于单调性的思维方式会在之后的Day05、Day10甚至面试中不断复用。明天我计划继续沿着题单推进把今天总结的模板用在更多二分变体上争取在下次周赛时不再犯T2那样的读题失误。毕竟打卡活动的意义不是一天刷十道题而是每天都能比前一天多搞懂一点东西。

二分查找与二分答案：从LeetCode 073到周赛430的实战蜕变

相关推荐

GEO与SEO的核心差异及AI时代内容优化实操指南

Redis RPOP count 批量弹出引发的延迟飙升与主线程阻塞剖析

工业智能网关实战：破解生产黑箱，打通数字化车间数据链路

更多资讯

OpenClaw + Claude Code + React AI工作流实战部署指南

NVIDIA AI芯片深度解析：从GPU并行计算到CUDA生态与部署实战

Minecraft Replay Mod 完全指南：安装、回放与关键帧运镜教程

5 分钟搭建本地 AI 智能体：OpenClaw 2.7.9 Windows 部署避坑与 TaoToken 网关配置

一阶线性偏微分方程特征线法：从通解到柯西问题全解析

wenyi 文译 Web 段落校阅实战：修订历史 + 实时进度，浏览器内完成全书校对

今日更新

企业AI转型实战指南：从场景选择到落地避坑的完整路线图

OpenRig：本地大模型服务编排的轻量级运行时框架

夸克网盘1TB免费扩容领取全攻略：新老用户实操流程与避坑指南

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？