要是给 LeetCode 里的基础算法排一个榜单二分查找绝对能进“看着最简单、翻车率最高”的前三名。力扣热门 100 题里有它周赛 430 里也出现了二分查找的变体很多人的题单里从 704 二分查找一直做到 073 爱吃香蕉的狒狒但真正把边界条件讲清楚的文章其实不多。这篇文章我想用自己刷题和带新人的经验把二分查找这套东西从底层逻辑讲到实战落地顺便把经典题型、模板代码、常见 Bug 全部整理出来。适合刚开始刷 LeetCode 的算法新手也适合面试前想系统过一遍二分查找的选手。1. 二分查找题为什么总在力扣热门 100 题里出现1.1 看似简单但大多数人卡在边界条件二分查找的原理一句话就能说完在一个有序数组里每次把搜索区间砍掉一半时间复杂度从 O(n) 降到 O(log n)。我记得自己第一次在力扣上做 704 二分查找的时候五分钟就写完了一提交直接报错明明思路是天衣无缝的。后来才发现问题出在left right还是left right、right mid还是right mid - 1这种最基础的细节上。这个现象在算法题里特别典型。二分查找的结构太简单了简单到很多人不会认真去验证边界但恰恰是这些边界决定了你能不能通过。力扣经典的 34 题“在排序数组中查找元素的第一个和最后一个位置”要求用 O(log n) 复杂度很多人第一反应是“我找到 target 之后向左右线性扩展不就行了”但最坏情况下这样会退化到 O(n)。这就是二分查找题和普通查找题的分水岭它考察的不是你会不会查而是你能不能精确控制查找的区间。1.2 面试和竞赛里对二分查找的考察层次从力扣的题目分布来看二分查找的题目数量不算多但出现频率非常高。简单题有 704 二分查找、35 搜索插入位置中等题有 34 找边界、33 搜索旋转排序数组、153 寻找旋转排序数组中的最小值难题和各种变体就更不用说了比如 875 爱吃香蕉的狒狒、1011 在 D 天内送达包裹的能力、410 分割数组的最大值。这些题表面上长相完全不同但核心套路是同一个先判断问题是否具备单调性再设计一个check(mid)函数最后把“求最优解”变成“判断某个候选值是否可行”。我在准备面试的过程中发现真正把这一套理解透了是可以在 10 分钟内搞定 875 这类二分答案题的。这就是为什么值得单独为二分查找写一篇题解向的总结。2. 两套二分查找模板记住循环不变量就不会错2.1 左闭右闭区间写法 [left, right]我最早使用的模板是左闭右闭区间这也是很多人入门时最常见的写法。核心思路是left和right都指向当前可能包含答案的区间内元素所以循环条件要用left right因为当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这套模板的循环不变量很好记每次循环开始时target 一定在[left, right]里如果存在的话。所以当nums[mid] target时说明 target 在 mid 的右边mid 本身不可能直接把左边界挪到mid 1反之把右边界挪到mid - 1。我见过很多人在写这一版时把right mid错写成right mid - 1或者反过来这都是因为没有严格遵守“mid 已经检查过不可能再是答案”这一事实。2.2 左闭右开区间写法 [left, right)另一种常见模板是左闭右开区间也就是right本身不包含在搜索范围内。这种写法在 C 的标准库里有直接对应lower_bound和upper_bound用的就是这种语义。循环条件写作left right因为当left right时区间已经空了。def binary_search_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这套模板的亮点在于它天然就是“找第一个大于等于 target 的位置”也就是lower_bound。你把return left改为return left if left len(nums) and nums[left] target else -1就变成了标准的二分查找如果直接返回 left就能解决 35 题“搜索插入位置”。我自己实际用下来边界题用左闭右开写起来最不容易乱因为right mid这种写法保持了右边界的不变性区间始终是合法的[left, right)。2.3 模板的选择标准与记忆技巧很多初学者会纠结“到底用哪套模板”我的建议是日常刷题先固定一套标准查找就用左闭右闭边界查找和二分答案就用左闭右开。这不是因为哪套更好而是因为你需要把一套逻辑的“循环不变量”吃透形成肌肉记忆。面试时最怕的就是临时切换模板然后在left、right、mid的赋值上精神内耗。记忆技巧就一个弄清楚你的right到底指向“普通元素”还是“哨兵位置”。如果是普通元素right len(nums) - 1对应的就是左闭右闭如果是哨兵位置right len(nums)对应的就是左闭右开。同理mid已经判断过就排除它left mid 1或right mid - 1mid可能成为答案就保留它left mid或right mid。这两个判断背后就是区间不变性的核心。3. 力扣二分题三大题型拆解标准型、边界型、答案型3.1 标准查找型704 二分查找与 35 搜索插入位置标准查找型是二分查找最直接的形态。704 题就是给你一个有序数组和一个 target找到就返回下标找不到返回 -1。这题用左闭右闭模板 10 分钟就能写完但它真正的价值在于让你验证自己对循环不变量的理解。我在带人刷题时发现很多人写 704 能过但把 target 换成“找第一个大于等于它的位置”就懵了这说明他对模板是背下来的不是理解下来的。35 题搜索插入位置就比 704 多了一层思考如果 target 不存在返回它应该插入的位置。这个位置其实就是第一个大于等于 target 的下标也就是lower_bound。用左闭右开模板可以直接得到答案def search_insert(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如果你能理解这段代码为什么对说明你已经理解了“区间收窄”的本质。顺便说一句35 题虽然标的是简单题但在面实际开发岗位的候选人里能一次写对的人并不算多足见边界问题的杀伤力。3.2 边界查找型34 找第一个和最后一个位置、33 搜索旋转排序数组34 题的要求是在一个可能包含重复元素的有序数组里找出 target 的起始下标和结束下标。如果找不到就返回 [-1, -1]。我先说一个最蠢但很多人最先想到的办法先用二分找到任意一个 target然后从它左右线性扫。这个做法在面试场景里基本等于送命因为最坏情况数组全等于 target线性扫描会让 O(log n) 变成 O(n)根本不符合题目对复杂度的要求。正确做法是分别找左边界和右边界。找左边界就用lower_bound模板找右边界可以做一个等价转化找“第一个大于 target 的位置”再减一也就是upper_bound。写成代码就是def search_range(nums, target): def lower_bound(): 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 def upper_bound(): 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() if start len(nums) or nums[start] ! target: return [-1, -1] return [start, upper_bound() - 1]这里的关键点是upper_bound的判断条件从变成了意味着等于 target 的元素也会被跳过最后返回的是第一个大于 target 的位置。这个转化思路在力扣里反复出现必须熟练掌握。33 题搜索旋转排序数组是另一类经典变体。数组是“部分有序”的比如 [4,5,6,7,0,1,2]整个数组不是单调的但在任意 mid 处至少有一半是有序的。因此每次比较nums[left]和nums[mid]来决定哪边有序再判断 target 是否落在有序区间内从而选择收缩方向。这题的难点不是二分本身而是判断“哪半边有序”以及“target 在不在这个区间里”的逻辑组合。建议自己手写一遍而不是直接背答案因为面试时问得很细。3.3 二分答案型875 爱吃香蕉的狒狒、1011 在 D 天内送达包裹的能力二分答案型是二分查找里最值钱、也最容易被忽略的形态。它把“求最值”变成“判断某个值是否可行”核心前提是答案本身具有单调性。875 爱吃香蕉的狒狒就是这个类型的经典代表。题目大意是狒狒要在 h 小时内吃完若干堆香蕉每堆有piles[i]根它每小时能吃 K 根如果某一堆不够 K 根它就吃光这一堆然后这小时结束不会去别的堆。求最小的 K使得能在 h 小时内吃完。暴力做法是从 K1 开始逐个试复杂度太高更好的做法是观察单调性K 越大吃完所有香蕉所需时间越少反之越多。于是可以在[1, max(piles)]这个区间里二分 K每次用check(mid)计算“如果速度是 mid需要几小时”如果时间 h说明速度可能还能更慢往左搜否则说明速度不够往右搜。def min_eating_speed(piles, h): left, right 1, max(piles) def check(k): hours 0 for p in piles: hours (p k - 1) // k return hours h while left right: mid left (right - left) // 2 if check(mid): right mid else: left mid 1 return left1011 题“在 D 天内送达包裹的能力”思路完全一样包裹重量数组是顺序的船运载能力越大需要的天数越少。二分运载能力每次模拟一遍看看按顺序装船能否在 D 天内装完。这类题的推荐解法是“最小化最大值”或“最大化最小值”是贪心和二分的组合题在力扣热门 100 题里出现频率很高。4. 实操复盘从读题到 AC 的五个关键步骤4.1 第一步确认问题具备单调性不是所有题目都能用二分查找。你拿到一道题第一反应应该是问自己如果我把答案设为 X那么“答案小于 X 时是否一定不可行答案大于 X 时是否一定可行”如果存在这种单调关系二分就成立。以 875 题为例K1 时耗时最长K无穷大时耗时最短耗时段随着 K 单调递减这就是单调性。如果是 704 这种直接查找题单调性体现在数组本身有序上。如果是旋转数组 33 题数组不是全局有序但仍然可以借助“任意 mid 至少一边有序”的性质进行局部排除。总之二分不是一种搜索技巧而是一种“利用单调性收缩搜索空间”的思维方式。4.2 第二步确定二分的左右边界边界定得太宽会导致二分次数多但一般问题不大定得太窄会漏解这才是致命的。标准查找题里left从 0 开始right根据模板选len(nums)-1或len(nums)。二分答案题里下限通常是 1 或min(...)上限通常是max(...)或sum(...)。比如 875 题速度上限就是max(piles)因为比这再大的速度一定满足要求且答案不可能超过它。我见过有人把 875 题的上限写成sum(piles)虽然也能 AC但会白白多二分两三次而且逻辑上不干净。在力扣里二分次数多一点少一点不影响复杂度级别但正确的边界能让你的代码更好理解也更容易向面试官解释。4.3 第三步设计 check 函数注意数据类型check 函数是二分答案题的灵魂。它接收一个候选答案 mid返回 bool 值。设计 check 时要注意的是循环内是否会产生大数是否需要用 long long。以 875 题为例piles 的单堆数量可能很大h 也可能很大(p k - 1) // k这种向上取整的写法本身没问题但累加的 hours 要小心如果题目数据范围超过 int建议在 C 里用long long在 Python 里则不用太担心。再比如 1011 题模拟装船时对重量求和如果 weights 的元素是 10^4 级别D 天数是 10^5 级别那么累加结果有可能超过 int 范围写成int会在边界用例爆掉。这类问题在力扣的隐藏测试用例里经常出现检验的就是你埋没在细节里的功力。4.4 第四步根据 check 结果收缩区间写二分答案模板时我强烈建议用左闭右开区间因为check(mid)为真就能收缩right mid否则left mid 1逻辑非常干净。它对应的不变量是[left, right)之间始终包含可能的答案并且left左侧都是不可行的、right右侧都是可行的。这就是经典二分答案题的最终形态。一个小技巧如果在写的过程中不确定left和right应该怎么更新就停下来手推一个只有 3 个元素的样例把 left、right、mid 都写出来走一遍。这个动作会帮你发现赋值方向是不是写反了比在脑子里空想要高效得多。4.5 第五步提交前用三种样例自测我提交之前习惯用三种样例过一遍第一个是最普通的正常用例第二个是只有一个元素的极端用例第三个是找不到 target 或不满足条件的用例。这三个样例能覆盖掉大部分边界问题。比如 704 题你至少试一下nums[1], target1和target0这两种情况如果是 34 题再试一下所有元素都等于 target 的情况。这一步看起来简单但能帮你省下好几轮提交被报错的尴尬。在力扣上刷题很多人喜欢写完就提交靠评测结果反推错误我不太推荐这个习惯。实际情况是每次提交之间等评测反馈的时间足够你心算完一整个边界用例了。培养“提交前手测”的习惯对你的面试也有好处因为面试现场是没有评测机给你试错的。5. 典型案例073 爱吃香蕉的狒狒的二分答案解法5.1 题干还原与问题转化先看原题描述狒狒有 N 堆香蕉第 i 堆有piles[i]根香蕉警卫会在 h 小时后回来。狒狒每小时选择一堆香蕉以速度 K 根/小时开始吃。如果这堆香蕉少于 K 根狒狒就会把这堆全部吃完然后这一小时内不再吃其他堆。求在 h 小时内吃完所有香蕉的最小速度 K。这题的核心难点是你不能直接算出一个公式因为每小时只能吃一堆这个约束导致无法简单分配。换个角度看给定速度 K我们可以很容易地算出吃完所有香蕉需要的小时数。这个“小时数”关于 K 是单调递减的。于是题目转化为在 K 的取值范围里找到最小的 K使得耗时不超过 h。5.2 为什么用二分答案而不是直接模拟很多第一次看到这题的人会问为什么不用贪心或模拟假设你想直接模拟最优策略你必须在每个小时决定吃哪一堆这是一个非常复杂的决策过程而且题目要求的是最小速度而不是策略。二分答案的优雅之处在于它把困难的“求最优”问题变成了“多次验证一个确定值是否可行”的问题验证的复杂度只有 O(n)。这种思想在力扣其他题目里也反复出现。比如 410 题“分割数组的最大值”和 1482 题“制作 m 束花所需的最少天数”本质都是在二分答案。所以说 875 题不仅是力扣热门 100 题里的常客更是理解二分答案模型的最好入门题。5.3 完整代码与复杂度分析完整代码就是我在 3.3 节给的实现。我再补充几个细节left从 1 开始因为吃香蕉速度必须大于等于 1。right从max(piles)开始因为速度再快也不可能比一次吃光最大堆更高效。计算耗时用(p k - 1) // k这是向上取整的标准写法避免浮点数误差。如果check(mid)为真说明 mid 可行尝试找更小的 K于是right mid否则left mid 1。最终返回的left就是答案。时间复杂度是 O(n log max(piles))其中 n 是堆数。每次 check 要遍历一遍 piles二分次数不超过 log(max(piles)) 次。这个复杂度在力扣的要求下完全没有问题。我自己第一次做这题的时候卡在了一个容易忽略的地方循环条件是left right还是left right。因为用的是左闭右开模板所以循环内要保证区间左闭右开循环条件必然是left right。一旦把写进去在left right时还会再循环一次可能把 left 推到 right 右侧导致下标越界。5.4 从 875 引申周赛 430 里的二分变体周赛 430 的那道题也落在二分查找这个家族里只是场景换了。看完题目你会发现解题框架和 875 一模一样找一个变量它从小到大变化check 结果从 false 变成 true或反过来然后二分找临界点。区别在于 check 函数本身更复杂可能包含贪心模拟、前缀和预处理或者数据结构维护。这类变体题的通用解题流程是先看答案变量是什么再想 check 怎么写最后确认边界范围和初始值。很多人刷题只记住了模板遇到变体就不会套了其实是因为没有把自己的思维固化到“先 check 后收缩”这个层面。如果你能把 875 题的代码吃透周赛里再出现二分答案基本就是换个场景复现同一件事。6. 二分查找常见 Bug 排查清单与避坑实录6.1 死循环left mid 导致的无限循环这是我踩过最多次的坑。当你在左闭右闭区间里把更新写成left mid而不是left mid 1时一旦区间只剩下两个元素mid会等于left导致 left 永远不变程序死循环。比如nums[1,3]target3left0, right1, mid0如果nums[0] target后你写left midleft 还是 0就永远退出不了。排查方法很简单如果提交后超时优先检查是不是这类死循环。解决思路是记住一条铁律mid 检查过就不保留所以 left 的更新必须是mid 1反过来如果 check 表示 mid 可能是答案那 right 的更新可以是mid但 left 不能直接等于mid除非使用特殊的取上整写法。在二分答案里如果确实想用left mid那么mid要写成(left right 1) // 2取上整防止死循环。6.2 溢出left right 的防溢出写法很多人求 mid 时写(left right) // 2这在 left 和 right 很小时没问题但在某些题目数据范围大的场景下left right 可能直接溢出。比如数组长度接近 2^31-1 时left right 超过 int 范围。虽然力扣的很多题不会卡这么大的数组但面试官确实喜欢问这个点。正确写法是left (right - left) // 2。这个表达式先把两个端点的差值算出来再除以 2最后加到 left 上全程不会出现超过 right 的数量级。这个写法面试官通常默认你会写错扣分是小被误以为基础不扎实才是大问题。6.3 返回 left 还是返回 right这是二分查找题最常见的困惑之一。用左闭右开模板时循环结束时left right返回哪个都一样。但如果你中途不小心换了模板或改了 right 的初始值返回 left 和返回 right 就可能有差异。我的习惯是只要循环结束统一返回 left。因为左闭右开模板里left 才是“第一个满足/不满足条件的位置”。这样你在写二分答案时也不用纠结check 为真往左缩最后 return left永远是对的。6.4 check 函数里不开 long long二分答案题里最容易忽视的 bug 是数据类型。以 1011 题为例weights 的单个元素可能是 10^4总共可能有 5 * 10^4 个包裹sum 累加可能到 5 * 10^8int 勉强够但如果你在 check 里写int capacity 0再往里面加 weights[i] 时在某些 C 环境下会溢出。Python 没有这个问题但 C 和 Java 都要注意。建议在 check 函数里把累加变量声明为long long或者直接看题目数据范围有 10^9 级别的数一律用 64 位整型。这个习惯能帮你避开力扣评测里大量隐蔽的失败用例。6.5 重复元素和 lower_bound/upper_bound 的语义处理重复元素时很多人会搞混两个边界。力扣 34 题非常典型我建议你在本地把 lower_bound 和 upper_bound 的实现各写一遍再用一个全是相同元素的数组做测试。比如nums[2,2,2,2]lower_bound 返回 0upper_bound 返回 4所以 target 2 的区间是 [0, 3]。如果你把 upper_bound 的判断条件写成 target就会得到错误的结果 0导致区间变成 [0, -1]。这种错误很难一眼看出来但通过小样例手推基本都能发现。6.6 二分答案题边界条件的速查表为了方便后续复习我整理了一张我在实际刷题时会拿出来对照的表场景初始 left初始 right循环条件check 为真时check 为假时基础查找左闭右闭0len(nums)-1left right直接返回 mid收缩对应边界插入位置左闭右开0len(nums)left rightright midleft mid 1找第一个等于 target0len(nums)left rightright midleft mid 1二分答案求最小可行值1 或 minmax 或 sumleft rightright midleft mid 1二分答案求最大可行值1 或 minmax 或 sumleft rightleft mid 1注意取上整right mid我个人在实际刷题时发现这张表的最后两行特别有用。很多人刷完 875 题后去做 1482 题会觉得套路变了其实只是 check 的判断方向变了。求“最小可行值”时check 为真就收缩右边界求“最大可行值”时check 为真就收缩左边界。想清楚这一层二分答案题基本就通了一半。最后再分享一点经验二分查找的题目数量在力扣里不算最多但它是“一通则百通”的代表。把 704、35、34、33、875 这五题吃透再去碰其他二分变体题你会发现所有题目都在围着一个核心转单调性 check 函数 边界收缩。刷完这五题之后我建议你手动在编辑环境里把左闭右开模板默写五遍每一遍都口述清楚循环不变量是什么。这个过程有点机械但效果出奇地好能帮你把模板从“背下来的代码”变成“理解透的思路”。