1. 从“找书”说起二分查找的直觉与困境如果你在图书馆的书架上找一本特定的书你会怎么找假设书架上的书是按字母顺序排列的你大概率不会从第一本开始一本一本地翻。一个更高效的方法是直接走到书架中间看看这本书的字母是排在中间这本书之前还是之后。如果排在之前你就去左边那一半继续找如果排在之后你就去右边那一半继续找。每次都能排除掉一半的书直到找到目标。这个“每次砍一半”的思路就是二分查找Binary Search最朴素、最核心的思想。在算法世界里二分查找是解决有序数据查找问题的“屠龙刀”。它高效、优雅能将时间复杂度从线性查找的 O(n) 降低到对数级别的 O(log n)。听起来很美对吧但为什么很多初学者甚至是有一定经验的开发者在面对二分查找的代码实现时依然会感到困惑和不确定为什么一个看似简单的while (left right)和mid (left right) / 2的组合会衍生出那么多不同的“模板”为什么有时候是left mid 1有时候又是right mid - 1为什么明明逻辑看起来是对的程序却陷入了死循环或者返回了错误的结果这些困惑的根源在于二分查找的“思想”虽然简单但其“实现细节”却充满了陷阱。它要求我们对循环不变式、边界条件、中间值计算有极其精确的理解。一个微小的偏差就可能导致完全错误的结果。因此掌握一个或多个清晰、可靠、易于记忆的“二分模板”并将其内化为解决特定问题的直觉是算法学习和面试准备中至关重要的一环。这篇文章我将结合自己多年的刷题和教学经验为你彻底拆解二分查找的几种核心模板解释清楚每一个细节背后的“为什么”并分享如何根据不同的问题场景选择并正确应用这些模板。2. 二分查找的基石循环不变式与搜索区间在深入模板之前我们必须先理解两个最核心的概念循环不变式和搜索区间。这是所有二分模板正确性的根基。循环不变式指的是在循环的每一次迭代开始和结束时都保持为真的某个条件或属性。在二分查找中我们维护的最重要的不变式通常是目标元素如果存在一定在当前定义的搜索区间内。我们所有的操作无论是更新左边界left还是右边界right都必须保证这个不变式不被破坏。搜索区间则是由左边界left和右边界right所定义的一个闭区间或半开半闭区间它表示我们当前正在考虑的可能包含目标元素的范围。搜索区间的定义方式直接决定了我们后续代码中边界更新和循环终止条件的写法。最常见的两种搜索区间定义是左闭右闭区间[left, right]这意味着left和right指向的元素都在考虑范围内。初始时left 0,right n - 1n为数组长度。左闭右开区间[left, right)这意味着left指向的元素在范围内但right指向的元素不在。初始时left 0,right n。注意这里说的“开”和“闭”是数学区间概念。在代码中right的初始值不同后续的循环条件和边界更新也必须与之匹配形成一套自洽的规则。混用规则是导致错误的主要原因。为什么要有两种这主要是为了编码的方便和个人习惯。左闭右闭区间更符合直觉“从第一个到最后一个”而左闭右开区间有时能让代码更简洁例如right初始化为长度n避免n-1的运算。但无论选择哪一种一旦选定就必须在循环条件、mid计算和边界更新上保持逻辑一致。接下来我们将看到这两种定义如何具体体现在不同的模板中。3. 经典精确查找模板在有序数组中找一个确定的值这是二分查找最教科书式的应用场景给定一个无重复元素的升序数组nums和一个目标值target找到target在数组中的索引如果不存在则返回 -1。我们首先使用左闭右闭区间模板来实现。3.1 模板一左闭右闭区间[left, right]def binary_search(nums, target): left, right 0, len(nums) - 1 # 定义初始搜索区间为 [0, n-1] while left right: # 当区间有效时继续搜索 mid left (right - left) // 2 # 防止溢出等同于 (left right) // 2 if nums[mid] target: return mid # 找到目标返回索引 elif nums[mid] target: left mid 1 # 目标在右半部分调整左边界 else: # nums[mid] target right mid - 1 # 目标在左半部分调整右边界 return -1 # 搜索区间为空未找到目标逐行拆解与“为什么”left, right 0, len(nums) - 1初始化搜索区间为整个数组。因为区间是闭的所以右边界right必须是最后一个元素的索引len(nums)-1。while left right:这是循环条件。为什么是而不是因为我们的区间是[left, right]。当left right时区间[left, right]仍然包含一个元素即nums[left]这个元素还没有被检查过所以循环必须继续。只有当left right时例如left3, right2区间才为空循环才应终止。如果写成while left right:那么当left right时循环就结束了会漏掉检查这一个元素的情况。mid left (right - left) // 2计算中间索引。这里使用了一个小技巧来防止整数溢出。在诸如 Java、C 等语言中如果left和right都是很大的正数(left right)可能会超出整型的最大值导致溢出。而left (right - left) // 2在数学上等价但避免了直接相加。在 Python 中整数不会溢出但这是一个良好的编程习惯。if nums[mid] target:找到目标皆大欢喜直接返回。elif nums[mid] target:说明目标值在mid的右侧。因为数组是升序的且nums[mid]已经小于target所以mid本身及其左边的所有元素都可以被排除了。为了维护“目标在搜索区间内”的不变式我们需要将搜索区间的左边界移动到mid的右边第一个位置即left mid 1。这里的1是关键它确保了被排除的mid不再包含在新的区间内。else:对应nums[mid] target。同理目标在mid的左侧mid及其右边的元素都被排除。更新右边界为right mid - 1。return -1如果循环正常退出即left right意味着搜索区间为空目标不存在于数组中。这个模板清晰、对称是理解二分思想的最佳起点。它的循环不变式是在每一轮循环开始时如果target存在于nums中那么它的索引一定在[left, right]区间内。3.2 模板二左闭右开区间[left, right)现在我们看看使用左闭右开区间的写法。def binary_search(nums, target): left, right 0, len(nums) # 定义初始搜索区间为 [0, n) while left right: # 当区间不为空时继续搜索 mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 # 目标在右半部分 else: # nums[mid] target right mid # 目标在左半部分注意这里不是 mid-1 return -1关键差异点解析初始化right len(nums)。因为区间是右开的right指向的是第一个不被包含的元素所以初始右边界是数组长度区间[0, len(nums))正好覆盖整个数组。循环条件while left right:。为什么是因为对于区间[left, right)当left right时区间为空例如[2, 2)不包含任何整数。所以只要left right区间就至少包含一个元素nums[left]。边界更新右侧right mid。这是与闭区间模板最大的不同当nums[mid] target时我们知道目标在左侧。在新的右开区间[left, right)中right是不被包含的边界。我们将right更新为mid意味着新的搜索区间是[left, mid)。注意nums[mid]本身因为大于target已经被排除在新的区间外了而right mid恰好实现了这一点因为mid是开边界不被包含。如果这里写成right mid - 1那么nums[mid-1]这个本应被包含的元素就会被错误地排除在外。两种模板如何选择对于基础的精确查找两者都是正确的效率也相同。左闭右闭模板的边界更新1/-1更对称可能更容易记忆。左闭右开模板的循环条件while left right:更简洁一些。我个人在基础教学时更倾向于使用左闭右闭模板因为它对“区间”概念的体现更直观。但你必须熟练掌握其中至少一种并理解其每一个细节。4. 二分查找的进阶应用寻找边界与模糊匹配实际问题中纯粹的“找等于”很少见。更常见的是寻找边界的问题例如在一个有重复元素的升序数组中找到target第一次出现的位置左边界。找到target最后一次出现的位置右边界。找到第一个大于等于target的元素的位置。找到最后一个小于等于target的元素的位置。这类问题无法用简单的nums[mid] target来判断返回因为即使找到了一个target它也不一定是我们要的边界。我们需要调整策略将二分查找转化为“寻找第一个满足某条件的元素的位置”。4.1 寻找左边界第一个等于 target 的位置我们以左闭右开区间模板为基础进行改造。目标是在数组nums中寻找target的插入位置即第一个大于等于 target 的元素索引。如果target存在这个位置就是它的左边界。def left_bound(nums, target): left, right 0, len(nums) # 搜索区间 [left, right) while left right: # 区间不为空 mid left (right - left) // 2 if nums[mid] target: right mid # 收缩右边界尝试找到更左的满足条件的位置 else: # nums[mid] target left mid 1 # 条件不满足左边界右移 # 循环结束时left right # left 的含义是nums 中小于 target 的元素个数也是 target 应该插入的位置 # 检查 left 是否越界以及 nums[left] 是否等于 target if left len(nums): return -1 # target 比所有数都大 return left if nums[left] target else -1核心逻辑解析条件判断我们将条件从nums[mid] target改为nums[mid] target。这意味着只要中间值大于或等于目标值我们就认为它“可能”是我们要找的左边界或者更右边但为了找到第一个最左的我们需要向左收缩搜索区间。边界更新当nums[mid] target时说明mid满足条件但我们要找的是第一个满足条件的所以答案可能在mid或其左边。因此我们将右边界right设为mid在新的区间[left, mid)中继续寻找。注意mid本身仍在新的候选范围内因为区间是左闭的。当nums[mid] target时说明mid不满足条件答案肯定在mid右边所以left mid 1。循环终止与结果循环结束时left right。left的值代表什么它代表数组中严格小于target的元素个数。因为所有nums[mid] target的情况都使left增加了1最终left就停在了第一个 target的位置。这个位置就是target应该被插入以保持数组有序的位置也是我们寻找的左边界。最后需要验证如果left没越界并且nums[left]确实等于target那么left就是左边界索引否则target不存在于数组中。4.2 寻找右边界最后一个等于 target 的位置寻找右边界可以转化为寻找最后一个等于 target 的元素也就是第一个大于 target 的元素的位置减一。def right_bound(nums, target): left, right 0, len(nums) # 搜索区间 [left, right) while left right: mid left (right - left) // 2 if nums[mid] target: left mid 1 # 收缩左边界尝试找到更右的满足条件的位置 else: # nums[mid] target right mid # 条件不满足右边界左移 # 循环结束时left right # left 的含义是第一个大于 target 的元素的位置 # 我们要找的是最后一个等于 target 的位置即 left - 1 if left 0: return -1 # target 比所有数都小 return left - 1 if nums[left - 1] target else -1核心逻辑解析条件判断条件改为nums[mid] target。这意味着只要中间值小于或等于目标值我们就认为答案可能在mid或其右边我们要找最后一个满足target的实际上是找最后一个等于的。边界更新当nums[mid] target时mid满足条件但可能不是最后一个。为了找到更右边的我们将左边界向右移动left mid 1。当nums[mid] target时mid不满足条件太大了答案在左边所以right mid。循环终止与结果循环结束时left right。left的值代表第一个大于target的元素的位置。因此最后一个等于target的元素的位置就是left - 1。最后验证nums[left - 1]是否等于target。4.3 通用“寻找第一个满足条件的位置”模板观察上面两个边界查找我们可以抽象出一个万能模板用于解决“在有序数组中寻找第一个满足条件condition(mid)为真的索引mid”这类问题。def binary_search_first(nums, condition): 在有序数组 nums 中寻找第一个满足 condition(mid) 为 True 的索引。 如果不存在返回 len(nums) (即假设的插入位置)。 condition 是一个函数接受索引 mid返回布尔值。 left, right 0, len(nums) # [left, right) while left right: mid left (right - left) // 2 if condition(mid): right mid # 满足条件向左收缩寻找第一个 else: left mid 1 # 不满足条件向右寻找 return left # left 是第一个满足条件的索引或 len(nums)如何使用这个模板找左边界condition(mid)定义为nums[mid] target。调用后检查nums[left] target。找右边界可以定义condition(mid)为nums[mid] target那么返回的left是第一个大于target的位置右边界就是left - 1。找第一个大于等于 x 的值condition(mid)定义为nums[mid] x。找第一个大于 x 的值condition(mid)定义为nums[mid] x。这个模板的强大之处在于它将二分查找的核心——逐步缩小搜索范围——与具体的判断条件解耦了。你只需要根据问题定义好condition函数模板就能帮你找到“第一个”满足它的位置。5. 实战中的陷阱与经验心得理解了模板不代表实战中就能一帆风顺。下面是我在大量练习和教学中总结的几个最容易出错的地方和对应的技巧。5.1 死循环mid 的取整方式与边界更新这是二分查找最经典的陷阱。考虑以下情况使用左闭右开模板while left right: mid (left right) // 2 # 向下取整 if some_condition: right mid else: left mid # 注意这里不是 mid 1当left 3, right 4时mid (34)//2 3。如果进入else分支left mid 3。你会发现left和right的值没有变化循环条件3 4依然成立下次计算mid还是 3陷入无限循环。根因与解决方案根因当区间长度缩小到 2即right - left 2时如果mid使用向下取整并且分支更新使得区间无法进一步缩小例如left mid就会导致死循环。解决方案1推荐在更新左边界时必须使用left mid 1。这能保证区间每次至少减少1。上面的万能模板和边界查找模板都遵守了这个规则。解决方案2使用向上取整计算mid即mid left (right - left 1) // 2。在某些特定的二分答案问题如“最大值最小化”中为了避免死循环会采用这种方式。但此时边界更新的逻辑也要相应调整通常对应left mid和right mid - 1。这形成了另一套模板需要配套使用不建议混用。经验法则对于while left right和mid left (right - left) // 2向下取整的组合更新左边界时务必用left mid 1。这是避免死循环的最安全做法。5.2 遗漏元素循环条件与区间定义的错配这是另一个常见错误。如果你使用左闭右闭区间[left, right]却写了while left right作为循环条件那么当left right时循环会提前终止nums[left]这个元素根本没有被检查过。反之如果使用左闭右开区间[left, right)却写了while left right那么当left right时区间本为空循环条件却依然成立会导致访问无效索引如nums[mid]其中mid len(nums)。记忆口诀闭区间用开区间用。初始化时right是n-1闭还是n开就决定了你用哪套规则。5.3 溢出问题mid 的计算在 C、Java 等语言中int mid (left right) / 2;在left和right都很大时可能导致整数溢出。因此通用的安全写法是int mid left (right - left) / 2;。在 Python 中虽然无此担忧但保持这种写法是良好的跨语言习惯。5.4 调试技巧打印关键变量当你对二分逻辑不确定时最有效的调试方法就是在循环内打印left,right,mid以及nums[mid]的值。观察搜索区间是如何收缩的是否按预期排除了不可能的一半。这对于理解复杂条件的二分查找如二分答案尤其有用。def debug_binary_search(nums, target): left, right 0, len(nums) step 0 while left right: mid left (right - left) // 2 print(fStep {step}: left{left}, right{right}, mid{mid}, nums[mid]{nums[mid]}) if nums[mid] target: right mid else: left mid 1 step 1 print(fFinal: left{left}) # ... 后续检查6. 从模板到直觉如何应对未知的二分问题掌握了模板最终目标是形成解决问题的直觉。当你遇到一个新的二分问题时可以遵循以下思考路径确定搜索空间首先要找的“答案”是什么是数组中的一个索引还是一个数值如最大值、最小值这个答案的可能范围是什么例如在“在有序数组中查找”类问题中搜索空间就是数组索引[0, n-1]。在“二分答案”类问题中如“吃香蕉”、“分割数组”搜索空间可能是[min_value, max_value]之间的所有整数。定义条件函数condition(mid)这是最关键的一步。问自己对于搜索空间中的一个候选答案mid我如何判断真正的答案是在mid的左边还是右边或者更具体地我要找的是第一个满足什么条件的mid例如在“寻找第一个大于等于 x 的数”中条件就是nums[mid] x。在“珂珂吃香蕉”问题中mid代表每小时吃的香蕉数条件可以是“以mid的速度能否在规定时间H内吃完所有香蕉”。如果能吃完说明速度可能可以更慢答案在左边否则需要更快答案在右边。选择并套用模板如果问题是“寻找第一个满足条件的索引”直接使用4.3 节的万能模板。如果问题是“寻找最后一个满足条件的索引”可以转化为“寻找第一个不满足条件的索引然后减一”或者调整条件函数和更新逻辑。始终明确你的搜索区间是[left, right)还是[left, right]并保持循环条件和边界更新的一致性。处理返回值模板返回的left或right循环结束时它们相等是“第一个满足条件的索引”。你需要根据问题的具体要求对这个返回值进行后处理检查是否越界left len(nums)或left 0。检查该位置的值是否真的等于目标对于查找类问题。直接返回left作为答案对于寻找插入位置或二分答案问题。7. 经典例题精讲与模板应用让我们用两个 LeetCode 经典题目来巩固一下。7.1 例题一在排序数组中查找元素的第一个和最后一个位置 (LeetCode 34)这正是我们前面讨论的寻找左右边界的直接应用。class Solution: def searchRange(self, nums: List[int], target: int) - List[int]: def find_first(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_last(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 # left 是第一个大于target的位置 return left - 1 first find_first(nums, target) # 检查 first 是否越界或值不匹配 if first len(nums) or nums[first] ! target: return [-1, -1] last find_last(nums, target) return [first, last]这里find_last函数使用了“寻找第一个大于target的位置”的模板然后减一得到最后一个等于target的位置。7.2 例题二寻找峰值 (LeetCode 162)题目要求峰值元素是指其值严格大于左右相邻值的元素。找到任何一个峰值元素的索引。数组可能包含多个峰值nums[-1] nums[n] -∞。这看起来不是有序数组但依然可以用二分。关键在于定义condition(mid)。思考对于位置mid我们比较nums[mid]和nums[mid1]。如果nums[mid] nums[mid1]说明右侧在上升那么峰值一定在mid的右边因为最右边是负无穷所以右边一定有峰值。如果nums[mid] nums[mid1]说明左侧在下降或者mid就是峰值那么峰值一定在mid的左边包括mid本身因为最左边也是负无穷。我们可以将“峰值在左边”视为一个条件。但更直观的方法是直接根据比较结果收缩区间。class Solution: def findPeakElement(self, nums: List[int]) - int: left, right 0, len(nums) - 1 # 使用闭区间因为要访问 mid1 while left right: # 当 left right 时即为峰值 mid left (right - left) // 2 if nums[mid] nums[mid 1]: # 下降趋势峰值在左边可能是 mid 本身 right mid # 注意区间是闭区间mid 仍在候选内 else: # 上升趋势峰值在右边 left mid 1 # 循环结束时left right指向峰值 return left为什么这个二分是有效的我们保证了循环不变式峰值元素始终存在于当前搜索区间[left, right]内。每次比较mid和mid1我们都能确定峰值在哪一半并舍弃另一半。当区间缩小到只有一个元素时left right该元素就是峰值。注意这里更新right mid而不是mid - 1因为mid有可能是峰值当nums[mid] nums[mid1]时。这道题展示了二分法并不局限于“有序数组”只要能够通过某个条件确定答案必然在左半部分或右半部分就可以使用二分来快速缩小搜索范围。