1. 项目概述为什么我们需要一个“二分模板”在算法学习和刷题的路上二分查找Binary Search绝对是一个让人又爱又恨的存在。爱它是因为它的思想简洁高效时间复杂度仅为 O(log n)是处理有序数据的神兵利器恨它是因为它的边界条件极其微妙一个不小心就会陷入“死循环”或者“差一错误”Off-by-one error。我见过太多人包括早期的我自己在写二分时反复调试明明逻辑看起来没问题但就是通不过某些刁钻的测试用例。问题的核心往往不在于“二分”这个思想本身而在于实现时的细节循环条件是left right还是left right更新边界时是mid还是mid 1返回值是left还是right这正是“二分模板”存在的意义。它不是一个死记硬背的咒语而是一套经过千锤百炼、逻辑自洽的“防御性编程”框架。掌握一个清晰、稳定的模板能让你在面对“寻找第一个大于等于目标值的元素”、“寻找最后一个小于目标值的元素”等变体问题时快速、准确地将思路转化为代码而无需在每次写二分时都重新推导边界从而将注意力集中在问题建模上。网络上热词如“二分查找pta函数”、“二分答案”、“带权二分”的流行恰恰说明了二分法及其变体在算法实践中的高频性和重要性。本文将为你彻底拆解一个我个人实践多年、稳定可靠的二分查找通用模板并深入探讨其在不同场景下的应用与变形。2. 核心模板拆解一套代码两种场景二分查找的核心思想是“减而治之”Divide and Conquer通过不断将搜索区间对半分割快速缩小目标范围。实现上的所有“坑”都源于对搜索区间定义的不同理解。我们首先明确一个最核心的概念搜索区间。我强烈建议并始终采用“左闭右开” [left, right)区间表示法。这意味着left指向当前搜索范围的起始索引包含。right指向当前搜索范围的结束索引不包含。因此初始搜索区间为[0, n)其中n是数组长度。区间为空的条件是left right。为什么选择“左闭右开”因为它与循环条件while (left right)以及后续的边界更新能形成完美的配合避免出现1/-1的混淆并且能自然地处理空区间和元素查找。这是模板稳定性的基石。基于此我们可以将二分查找的常见问题归结为两大类并对应两个细微差别的模板。2.1 模板一寻找确切值或任意一个目标这个模板用于在有序数组中查找一个确切等于目标值target的元素或者找到任意一个满足条件的元素当条件函数复杂时。它的目标是“找到即返回”。代码模板def binary_search_exact(nums, target): left, right 0, len(nums) # 初始化左闭右开区间 while left right: # 区间不为空时继续 mid left (right - left) // 2 # 防止溢出等同于 (leftright)//2 if nums[mid] target: return mid # 找到目标直接返回索引 elif nums[mid] target: left mid 1 # 目标在右侧收缩左边界 else: # nums[mid] target right mid # 目标在左侧收缩右边界 return -1 # 未找到目标关键点解析循环条件while left right只要区间[left, right)内还有元素至少一个就继续搜索。当left right时区间为空循环终止。中间位置计算mid left (right - left) // 2这是计算中点索引的标准安全写法能有效避免(left right) // 2在left和right很大时可能发生的整数溢出。边界更新当nums[mid] target说明目标值只可能出现在mid的右侧。因为我们的区间是左闭右开且mid已经检查过不等于目标所以新的左边界应该是mid 1排除mid。当nums[mid] target说明目标值只可能出现在mid的左侧。同样因为区间定义mid指向的元素不包含在下一轮搜索的右半部分所以新的右边界直接设为mid即可。返回值找到则返回索引循环结束未找到则返回-1。这个模板直观且易于理解是二分查找最基础的形式。但实际算法题中更常见的是下面这种“边界查找”问题。2.2 模板二寻找左侧边界或右侧边界更强大这是二分模板的精华所在用于解决诸如“寻找第一个大于等于target的元素的位置”、“寻找最后一个小于target的元素的位置”等问题。这类问题通常不关心是否精确相等而是寻找一个边界。我们可以通过一个条件函数is_blue(mid)来抽象这个问题将数组想象成由两部分组成前一部分蓝色不满足条件后一部分红色满足条件。二分查找的目标就是找到第一个红色元素左边界或者最后一个蓝色元素右边界。我们以寻找第一个满足条件即左边界为例这是最常用的变体。代码模板寻找左边界def binary_search_left_bound(nums, target): left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: # 条件元素 target 时视为“红色” right mid # 满足条件说明边界在 mid 或其左侧收缩右边界 else: # nums[mid] target left mid 1 # 不满足条件说明边界在 mid 右侧收缩左边界 # 循环结束时left right return left # 返回 left 或 right 均可它指向第一个“红色”位置关键点解析与模板一的差异条件判断的变化不再是简单的等于、小于、大于。这里我们用一个布尔条件nums[mid] target来划分“红蓝区域”。所有 target的元素是“蓝色” target的元素是“红色”。我们的目标是找到第一个“红色”元素。边界更新的统一逻辑如果条件(mid) 为真说明mid本身可能就是我们寻找的边界或者边界在mid左边。为了不丢失这个可能的边界我们将搜索区间的右边界收缩到mid(right mid)。如果条件(mid) 为假说明mid肯定不是我们要找的边界边界一定在mid的右边。因此我们将左边界收缩到mid 1(left mid 1)。循环不变性在整个循环过程中我们始终保持一个不变式left的左边如果存在都是“蓝色”不满足条件right及其右边如果存在都是“红色”满足条件。循环结束时left和right重合它们共同指向的就是第一个“红色”元素的位置。返回值及其含义返回的left是第一个满足nums[i] target的索引i。如果所有元素都小于target全是蓝色那么循环结束时left right len(nums)。这意味着“目标边界”在数组之外所有元素都不满足条件。如果返回的索引i在数组范围内需要检查nums[i]是否真的等于target如果我们找的是等于的情况。例如找target5在数组[2,4,6,8]中的插入位置此模板会返回2第一个5的位置但nums[2]6 ! 5。所以有时需要后处理if left len(nums) and nums[left] target: return left else: return -1。寻找右边界的模板可以类似推导通常转化为“寻找最后一个不满足条件的元素”最后一个蓝色或者通过寻找“第一个满足 target的元素”的位置再减一来实现。掌握左边界模板足以应对绝大多数情况。注意这两个模板的核心区别在于if条件内的逻辑和对应的更新语句。模板一在找到目标后立即返回模板二则持续收缩区间直到leftright最终返回的是一个边界位置。务必理解其背后的“红蓝分区”思想。3. 模板的实战应用与变形理解了核心模板后我们来看看如何用它们解决具体的算法问题。你会发现很多看似复杂的问题核心都是一个二分查找。3.1 基础应用在有序数组中查找元素这直接使用模板一即可。例如 LeetCode 704. 二分查找。class Solution: def search(self, nums: List[int], target: int) - int: 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 -13.2 进阶应用一寻找边界模板二的主场例题1LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置这个问题要求找出target的起始和结束位置。我们可以分解为两个子问题寻找第一个 target的位置左边界。寻找第一个 target的位置然后减一即为最后一个 target的位置右边界。class Solution: def searchRange(self, nums: List[int], target: int) - List[int]: def find_left(nums, target): left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: # 条件寻找第一个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: # 条件寻找第一个target的 right mid else: left mid 1 return left - 1 # 第一个target的位置减一就是最后一个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]例题2LeetCode 35. 搜索插入位置这个问题是寻找第一个 target的元素位置如果不存在则返回数组长度。这正是模板二左边界的直接应用无需后处理检查值是否相等。class Solution: def searchInsert(self, nums: List[int], target: int) - int: 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 # 这个left就是插入位置3.3 进阶应用二在抽象条件上二分二分答案这是二分查找威力最强大的地方。当问题的答案存在一个明确的单调性并且我们可以设计一个函数check(mid)来判断某个候选答案mid是否“可行”时就可以对答案进行二分搜索。核心思想假设答案可能的范围是[low, high]并且对于某个值x如果check(x)为真那么所有x或x的值也可能为真单调性。我们的目标就是找到满足check条件的边界值最大或最小可行解。通用步骤确定答案的搜索范围[left, right]。设计check(mid)函数判断mid作为候选答案是否可行。根据问题的单调性套用模板二。如果问题是“求最小的可行解”那么check(mid)为真时说明答案可能更小或就是mid应该收缩右边界 (right mid)为假时收缩左边界 (left mid 1)。如果问题是“求最大的可行解”那么check(mid)为真时说明答案可能更大或就是mid应该收缩左边界 (left mid)为假时收缩右边界 (right mid - 1)。注意此时区间表示和更新可能需要微调通常转化为求“最小不可行解-1”来处理以保持左闭右开模板的一致性。例题LeetCode 875. 爱吃香蕉的珂珂珂珂每小时最多吃一堆香蕉如果吃不完会留到下一小时。给定香蕉堆数组piles和时限h求珂珂每小时最少需要吃多少根香蕉K才能在h小时内吃完。分析搜索范围K最小是 1最大是max(piles)因为每小时最多吃一堆吃一堆的时间取决于该堆的数量K再大也没用。单调性如果每小时吃speed根香蕉可以在h小时内吃完那么吃speed1根也一定可以。反之如果speed根不行那么speed-1根更不行。存在单调性。检查函数check(speed)计算以速度speed吃完所有香蕉需要的小时数need_hours sum((pile speed - 1) // speed for pile in piles)。判断need_hours h是否成立。问题转化求最小的满足check(speed)为真的speed。套用寻找左边界的模板。class Solution: def minEatingSpeed(self, piles: List[int], h: int) - int: left, right 1, max(piles) # 搜索范围 while left right: mid left (right - left) // 2 # 计算以速度mid吃完需要的时间 need_hours sum((pile mid - 1) // mid for pile in piles) if need_hours h: # 条件满足可行 right mid # 寻找更小的可行解收缩右边界 else: left mid 1 # 当前速度太慢增加速度收缩左边界 return left # 返回最小的可行速度类似的问题还有“分割数组的最大值”LeetCode 410、“在 D 天内送达包裹的能力”LeetCode 1011等它们都是“二分答案”的经典例题。网络热词中的“二分答案”指的就是这类问题。4. 常见“坑点”与调试技巧即使有了模板在实际编码中依然可能出错。下面是我在大量练习和教学中总结出的常见问题和应对策略。4.1 死循环问题死循环通常发生在while (left right)且更新语句为left mid或right mid - 1时。在我们的标准模板中我们强制使用left mid 1或right mid这通常能避免死循环。但如果你自行修改了更新逻辑需要特别注意当left和right相邻时mid的计算由于向下取整会等于left。如果此时更新left mid区间将不会缩小导致无限循环。黄金法则在while (left right)循环中确保每次迭代区间[left, right)的长度至少减少 1。我们的标准更新方式 (leftmid1或rightmid) 保证了这一点。4.2 差一错误Off-by-one这是二分查找最常见的错误。根源在于对搜索区间开闭的定义不清晰。初始化错误如果区间定义为“左闭右闭”[left, right]那么right初始应为len(nums)-1循环条件应为while (left right)更新语句可能包含right mid - 1。混用两种定义必然出错。返回值含义不明确使用模板二时循环结束后的left指向的是“第一个满足条件的索引”。你需要根据问题语境判断这个索引是否就是最终答案。例如在搜索插入位置时它直接就是答案在查找确切元素时你需要验证nums[left] target。避坑技巧始终坚持使用“左闭右开”[left, right)区间和配套的模板。这套体系逻辑一致记忆负担小能覆盖绝大多数场景。将其作为你的默认选择。4.3 溢出问题计算中点时使用mid (left right) // 2在left和right都是很大的整数时left right可能会超出编程语言中整型的最大值导致溢出。这在C、Java等语言中需要特别注意。解决方案使用mid left (right - left) // 2。这个公式在数学上等价但避免了先加后除可能导致的溢出。在Python中整数精度很高通常不会溢出但养成这个习惯是良好的编程实践。4.4 调试方法当你怀疑二分查找出错时可以尝试以下方法打印日志在循环内部打印left,right,mid的值以及条件判断的结果。观察区间是如何收缩的是否按预期进行。测试边界用例空数组[]。只有一个元素的数组[5]分别查找存在和不存在的值。两个元素的数组[1,3]查找每个元素以及中间不存在的值。查找的值小于数组最小值、大于数组最大值。数组中有重复元素查找其边界。使用“循环不变式”验证在脑海中或注释中明确你的循环不变式。对于模板二不变式是“left左侧元素都不满足条件right右侧元素都满足条件”。每次循环后检查这个不变式是否仍然成立。5. 模板的扩展与相关算法思想二分查找的模板思想可以延伸到更广泛的场景。5.1 在非有序数组上的应用局部有序或山脉数组有些数组并非全局有序但具有某种局部有序或单调性依然可以使用二分。例如旋转排序数组LeetCode 33, 81数组在某点旋转后总有一半是有序的。通过比较nums[mid]与nums[left]或nums[right]可以判断哪一半是有序的进而确定目标值在哪一半。寻找峰值LeetCode 162山脉数组或任意数组只要比较nums[mid]和nums[mid1]就能判断峰值在左侧还是右侧。搜索二维矩阵LeetCode 74, 240将二维矩阵视为一个一维数组进行二分关键在于如何将一维索引mid映射到二维坐标(i, j)。这类问题的关键在于找到可以用于决策的单调性。虽然比较的逻辑更复杂但收缩区间的框架left mid 1或right mid依然适用。5.2 与其他算法结合二分查找作为一种高效的搜索策略常作为其他算法的子过程“LISDP 二分优化”这是求解最长递增子序列LIS的O(n log n)算法。它维护一个“潜在序列”数组tails其中tails[i]表示长度为i1的所有递增子序列中末尾元素的最小值。这个数组是递增的。当处理一个新元素x时在tails中二分查找第一个 x的位置并替换之使用我们的模板二。这完美地将DP的复杂度从 O(n²) 降到了 O(n log n)。“带权二分”通常指在优化问题中如果目标函数关于某个参数是凸的或具有单调性可以通过二分这个参数来逼近最优解类似于“二分答案”。5.3 三分查找与二分查找的对比对于单峰函数先增后减或先减后增求极值点的问题可以使用三分查找。它每次迭代将区间分成三份通过比较两个中间点的函数值可以舍弃掉不可能包含极值点的三分之一区间。其时间复杂度也是 O(log n)但常数比二分查找大。二分查找适用于单调序列上的查找三分查找适用于单峰函数求极值。选择哪种方法取决于问题的性质。掌握一个坚实的二分模板就像是拥有了一把打开许多中高级算法问题大门的钥匙。它背后的“减治”思想和“边界收缩”逻辑是算法思维的重要组成部分。我个人的经验是初期可以刻意练习强迫自己在遇到有序或具有单调性的问题时首先考虑二分法的可能性并套用模板进行实现。经过几十道题的训练后你会对区间的开闭、条件的设置、边界的更新产生一种“肌肉记忆”从而能够快速、准确地解决这类问题。最后记住模板是工具理解其背后的原理搜索区间、循环不变式、红蓝分区才是让你灵活运用的根本。