尧图网站开发 
如果你是一个 Python 初学者或者已经在写业务代码但很少接触算法我想先抛出一个很直接的观点二分查找不是一个“会背模板就行”的知识点而是一个值得反复练习、直到形成肌肉记忆的基础算法。很多人在学习二分查找时都有过这样的经历看教程时觉得很简单就是“三个变量、一个循环、不断缩小区间”可一旦自己动手写或者去 LeetCode、PTA 上做题就会遇到各种莫名其妙的问题——死循环、下标越界、查不到目标值、边界情况漏掉。更扎心的是代码看着和别人的一模一样运行结果却不对。这篇文章不会只给你一个模板。我会从头梳理二分查找的适用条件、核心逻辑、完整实现、常见变体以及 Python 标准库bisect的用法。每一步都讲清楚“为什么要这么写”而不是让你死记硬背。读完这篇文章你应该能达成三个目标不用查资料写出正确的二分查找代码能够处理“查找第一个等于目标值的元素”“查找最后一个等于目标值的元素”这类变体问题在实际项目里知道什么时候应该自己手写什么时候应该直接使用bisect模块。1. 二分查找到底解决了什么问题在进入代码之前先说说二分查找的定位。二分查找也叫折半查找是一种在有序数组中查找特定元素的高效算法。它的核心思想是每次把待查找的区间缩小一半通过比较中间元素与目标值的大小关系决定下一步是向左半边继续查找还是向右半边继续查找。这个算法解决的最核心问题是在大规模有序数据中快速定位目标值。举个例子。假设你有一个长度为 100 万的已排序列表需要判断某一个数字是否存在。最直接的做法是遍历整个列表最坏情况下要比较 100 万次。如果使用二分查找最多只需要比较 20 次左右。这个差距在数据量越大时越明显。很多人可能会说现在机器性能这么强100 万次比较算什么但真实场景远没有这么简单。你需要考虑的是如果这个列表有 1 亿条数据呢如果这个查找操作在一秒钟内被调用成千上万次呢如果数据不是存在内存里而是需要查询远程数据库或外部存储呢在这些场景下O(n) 和 O(log n) 的差距就不是“快一点”的问题而是“能不能扛得住”的问题。所以二分查找看似是一个基础算法但它的思想渗透在很多底层系统和工具中数据库的索引查找、操作系统的文件系统分配、Git 的二分调试、各种数值计算库中的求根算法都能看到二分思想的影子。这也是为什么很多面试和笔试环节会专门考察二分查找——它不只是考你会不会写循环而是考察你能否处理边界、维护区间不变量、分析复杂度。1.1 暴力查找 vs 二分查找在没有学习二分查找之前大部分人查找元素的写法是这样的def find(nums, target): for i in range(len(nums)): if nums[i] target: return i return -1这种线性查找有两个特点代码简单不需要任何前置条件时间复杂度是 O(n)数据量大了以后性能直线下降。二分查找则有两个严格的前置条件数据必须存储在支持随机访问的结构中比如 Python 的list。链表不行因为无法直接通过下标访问中间元素。数据必须是有序的。这里的“有序”可以是升序也可以是降序但必须有一个确定的比较规则。我把两者的对比整理成下表对比维度线性查找二分查找前置条件无序、有序都可以必须有序且支持随机访问时间复杂度O(n)O(log n)代码复杂度极低中等需要注意边界适用数据量小规模数据中大规模数据常见实现方式for 循环遍历while 循环 区间收缩一个常见的误解是“二分查找只能用于数组”。实际上只要数据结构支持通过下标快速访问元素且元素之间可以比较大小二分查找的思想都可以应用。Python 的list、tuple、array都可以。1.2 为什么二分查找的时间复杂度是 O(log n)这个结论不需要死记理解推导过程就够了。假设数组长度为 n。第一次比较后如果没有找到目标值搜索范围缩小到 n/2第二次比较后缩小到 n/4第三次是 n/8……以此类推。最坏情况下我们需要一直缩小范围直到区间里只剩下一个元素。这个过程经过 k 次比较后区间大小变为 n / 2^k。当 n / 2^k 1 时也就是 2^k n解得 k log2(n)。因此在最坏情况下二分查找最多需要 log2(n) 1 次比较。在大 O 表示法中我们省略底数和常数记作 O(log n)。这个复杂度意味着什么当 n 10 亿时log2(n) 大约为 30。也就是说哪怕数据量到了十亿级别二分查找也只需要 30 次左右的比较就能定位到目标值。这也是它能在很多高性能系统中被广泛使用的原因。2. 手写第一个二分查找从最简版本开始现在进入实操环节。我们先从最经典的场景开始在一个升序排列的数组中查找目标值返回下标如果不存在返回 -1。这是 LeetCode 704 题、PTA 等平台的基础题型也是很多面试手写算法时的第一问。它的代码看起来很简单但隐藏了不少值得反复确认的细节。2.1 最简实现def binary_search(nums, target): left 0 right 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 0right len(nums) - 1。这里使用的是闭区间[left, right]也就是说目标值可能在区间内的任意一个位置包括left和right本身。第二while 循环的退出条件。while left right表示只要区间还没有被收缩到空集就继续查找。这里为什么用而不是因为当left right时区间里还有一个元素这个元素还没有被比较过不能退出循环。第三中间位置的计算。mid left (right - left) // 2。有些同学可能会写成mid (left right) // 2。两者在大多数情况下结果一样但前者更安全。为什么因为当left和right都是很大的整数时left right可能超出语言所能表示的整数上限导致溢出。虽然 Python 的整数不会溢出但这个习惯在 C、Java 等语言中非常重要。从写代码的第一天就养成好习惯没有坏处。第四区间收缩规则。当nums[mid] target时说明目标值在 mid 的右侧所以把左边界收缩到mid 1当nums[mid] target时说明目标值在 mid 的左侧所以把右边界收缩到mid - 1。这里特别需要注意的是收缩时要把mid排除在外而不是直接赋值为mid。否则如果目标值不存在循环可能永远无法退出。2.2 为什么一定可以终止每次循环区间要么缩小到左半部分要么缩小到右半部分并且都是从[left, right]变成[left, mid - 1]或[mid 1, right]。因为mid始终位于区间内部所以无论走哪个分支新区间的长度都严格小于旧区间的长度。这就保证了循环一定会结束。反过来如果某段代码把left mid或right mid那么当区间长度缩小到 1 时mid left right新的区间和旧区间完全一样就会陷入死循环。这是一个非常经典的二分查找 bug后面会详细展开。2.3 验证一下我们可以用一组简单的测试数据来验证上面的代码nums [1, 3, 5, 7, 9, 11, 13] target 7 print(binary_search(nums, target))预期输出为3因为nums[3]的值正好是 7。再测一个不存在的情况print(binary_search(nums, 8))预期输出为-1这个最简单的版本已经能覆盖大多数“判断一个数在不在有序数组里”的需求。但实际场景中我们经常会遇到更复杂的情况比如数组里有重复元素需要找到第一个等于目标值的位置或者最后一个等于目标值的位置。这就引出了二分查找的变体问题。3. 高频变体查找第一个等于目标和最后一个等于目标先看一个实际场景。假设你有一个学生的成绩列表已经按分数升序排列里面有很多重复分数。现在需要找到第一个等于 90 分的位置或者最后一个等于 90 分的位置。如果用最基础的二分查找因为nums[mid] target时就直接return mid你只会返回任意一个等于目标值的位置无法保证是第一个或最后一个。面试中经常考察的“二分查找左边界/右边界”问题就是在这个背景下提出的。3.1 查找第一个等于目标值的位置思路是即使找到了等于target的元素也不立刻返回而是继续把右边界向左收缩直到区间为空。这样最后一次满足nums[mid] target的位置就是最左边的那个。def first_position(nums, target): left 0 right len(nums) - 1 ans -1 while left right: mid left (right - left) // 2 if nums[mid] target: if nums[mid] target: ans mid right mid - 1 else: left mid 1 return ans这里的关键变化是当nums[mid] target时都往左半区继续找。等于的情况用ans记录下来然后继续向左压缩看左边还有没有相等的元素。如果左边没有相等的元素了最后一次记录的ans就是第一个等于目标值的位置。如果整个数组里没有目标值ans会一直保持-1最后返回-1。3.2 查找最后一个等于目标值的位置思路对称找到等于target的元素后不立刻返回而是继续把左边界向右收缩。def last_position(nums, target): left 0 right len(nums) - 1 ans -1 while left right: mid left (right - left) // 2 if nums[mid] target: if nums[mid] target: ans mid left mid 1 else: right mid - 1 return ans这里的核心变化是当nums[mid] target时都往右半区继续找。等于的情况记录到ans然后继续向右压缩确保最终记录的是右边的最后一个。3.3 变体问题为什么重要直接回答这个问题变体问题是区分“背模板”和“真理解”的分水岭。如果你只会最基础的版本遇到“查找第一个大于等于目标值的元素”“查找最后一个小于目标值的元素”“插入位置”等新题时就会不知所措。而只要你理解了“区间收缩”的本质——什么时候收缩左边界什么时候收缩右边界什么时候记录答案——你就能把二分查找迁移到任何边界查询问题上。在 Python 的实际项目中这类变体逻辑通常不需要你手写因为标准库bisect已经提供了现成的方法。但理解实现原理能帮助你判断应该调用bisect_left还是bisect_right以及如何结合返回值判断目标值是否存在。4. 用 Python 标准库 bisect 完成二分查找Python 的bisect模块提供了一套基于二分查找的实用函数常用于在有序列表中查找插入位置、定位左右边界等场景。很多 Python 开发者知道这个模块存在但实际使用频率并不高。这其实很可惜因为bisect不仅代码简洁性能还非常可靠。4.1 bisect 的常用函数bisect模块中最常用的两个函数是bisect_left和bisect_right。bisect_left(a, x)返回将x插入到有序列表a中的最左侧位置使得插入后列表仍然有序。如果a中存在等于x的元素返回的是第一个等于x的元素的下标。bisect_right(a, x)返回将x插入到有序列表a中的最右侧位置。如果a中存在等于x的元素返回的是最后一个等于x的元素下标加一。来看一个简单例子import bisect nums [1, 3, 3, 5, 7, 9] print(bisect.bisect_left(nums, 3)) # 输出 1 print(bisect.bisect_right(nums, 3)) # 输出 3这里bisect_left返回 1说明第一个等于 3 的位置下标是 1bisect_right返回 3说明最后一个等于 3 的位置下标是 2加一后是 3。4.2 用 bisect 实现“查找目标值是否存在”import bisect def binary_search(nums, target): pos bisect.bisect_left(nums, target) if pos len(nums) and nums[pos] target: return pos return -1 nums [1, 3, 5, 7, 9] print(binary_search(nums, 7)) # 输出 3 print(binary_search(nums, 8)) # 输出 -1这里有一个细节需要注意bisect_left返回的位置有可能是数组长度len(nums)表示目标值比数组中所有元素都大插入位置在末尾。因此在判断nums[pos] target之前必须先检查pos len(nums)否则会触发下标越界。4.3 bisect 在“插入元素保持有序”场景中的使用假设你维护了一个有序列表需要频繁插入新元素同时保持列表有序。最粗暴的方式是列表追加后再排序但时间复杂度较高。使用bisect可以精确定位插入位置import bisect nums [1, 3, 5, 7, 9] bisect.insort(nums, 4) print(nums) # 输出 [1, 3, 4, 5, 7, 9]insort函数会先调用bisect_left或bisect_right找到插入位置然后在对应位置执行插入操作。注意列表插入操作本身是 O(n) 的因为需要移动后续元素bisect只解决了“找到插入位置”这一部分的 O(log n)整体性能依然受制于列表结构。如果插入非常频繁应该考虑使用heapq堆或sortedcontainers等更合适的数据结构。4.4 什么时候选择手写什么时候选择 bisect这是一个非常实际的问题。我的建议是如果你只是需要在有序列表里快速定位插入位置或者查找左右边界直接用bisect不需要手写。如果你是学习算法或者面试手写代码必须让自己熟练手写二分查找。如果你的查找逻辑不是标准的“等于、第一个等于、最后一个等于”而是更复杂的条件比如“查找第一个满足某个自定义谓词的元素”使用bisect可能不太方便手写会更灵活。5. 二分查找最常见的坑死循环与下标越界二分查找之所以被称为“思路简单但实现容易出错”的算法是因为它有一些隐蔽的边界问题。即使是有多年经验的开发者偶尔也会在细节上翻车。下面列出几个最常见的坑并分析原因。5.1 死循环死循环通常是区间收缩写错导致的。最典型的情况是left mid或right mid。看一个错误示例def wrong_binary_search(nums, target): left 0 right len(nums) - 1 while left right: mid (left right) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid # 错误应该写成 mid 1 else: right mid # 错误应该写成 mid - 1 return -1当区间缩小到[left, right]且nums[mid]不等于目标值时如果left mid而 mid 恰好等于 left那么新区间和旧区间完全相同循环无法退出最终形成死循环。解决办法是在闭区间[left, right]的模板中收缩时必须排除掉已经比较过的mid也就是left mid 1或right mid - 1。5.2 下标越界下标越界通常发生在以下两种情况。第一种数组为空时直接访问nums[mid]。比如传入nums []right -1while left right的条件不成立循环根本不执行所以不会越界。但如果代码里在进入 while 之前就访问nums[0]就会越界。第二种使用了bisect_left或bisect_right之后没有判断返回位置是否等于len(nums)就访问nums[pos]。前面已经强调过bisect_left返回的位置可能等于数组长度此时nums[pos]会触发IndexError。5.3 取中间值时溢出在 C 或 Java 中(left right) // 2在left right超过整数上限时会产生溢出。虽然 Python 整数没有这个问题但在阅读其他语言代码或手写算法时很多人会下意识用这种方式。为了避免坏习惯建议统一写成left (right - left) // 2。5.4 忘记思考空数组和单元素数组二分查找的边界测试中空数组和单元素数组是最高频的出错点。写完之后建议至少跑一遍这两种输入print(binary_search([], 5)) # 应该输出 -1 print(binary_search([5], 5)) # 应该输出 0 print(binary_search([5], 3)) # 应该输出 -1很多看起来没问题的代码在这三组测试上会现出原形。6. 完整示例一个可直接运行的 Python 脚本把上面的内容串起来写一个包含基础二分查找、左右边界查找、bisect 用法的完整 Python 脚本。你可以直接把代码复制到本地运行。# -*- coding: utf-8 -*- 二分查找有序数组 示例脚本 运行环境Python 3.6 import bisect def binary_search(nums, target): 在有序数组 nums 中查找 target返回下标不存在返回 -1。 left 0 right 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 def first_position(nums, target): 返回第一个等于 target 的下标不存在返回 -1。 left 0 right len(nums) - 1 ans -1 while left right: mid left (right - left) // 2 if nums[mid] target: if nums[mid] target: ans mid right mid - 1 else: left mid 1 return ans def last_position(nums, target): 返回最后一个等于 target 的下标不存在返回 -1。 left 0 right len(nums) - 1 ans -1 while left right: mid left (right - left) // 2 if nums[mid] target: if nums[mid] target: ans mid left mid 1 else: right mid - 1 return ans def bisect_search(nums, target): 使用 bisect 模块实现查找。 pos bisect.bisect_left(nums, target) if pos len(nums) and nums[pos] target: return pos return -1 if __name__ __main__: test_data [1, 3, 3, 5, 7, 9, 9, 11] print(基础二分查找) print(binary_search(test_data, 7)) # 4 print(binary_search(test_data, 8)) # -1 print(第一个等于目标值) print(first_position(test_data, 3)) # 1 print(first_position(test_data, 9)) # 5 print(first_position(test_data, 10)) # -1 print(最后一个等于目标值) print(last_position(test_data, 3)) # 2 print(last_position(test_data, 9)) # 6 print(last_position(test_data, 10)) # -1 print(bisect 模块查找) print(bisect_search(test_data, 7)) # 4 print(bisect_search(test_data, 8)) # -1 print(边界测试) print(binary_search([], 5)) # -1 print(binary_search([5], 5)) # 0 print(binary_search([5], 3)) # -1运行这个脚本正常的输出应该是基础二分查找 4 -1 第一个等于目标值 1 5 -1 最后一个等于目标值 2 6 -1 bisect 模块查找 4 -1 边界测试 -1 0 -1如果你得到的输出和这里不一致说明某个函数实现有问题可以对照前面的代码逐行检查。6.1 如何验证代码的正确性除了手动测试还可以用更系统的方式验证生成一个随机有序数组再暴力遍历确认每个函数的结果是否正确。import random def verify(): for _ in range(1000): size random.randint(0, 30) nums sorted(random.randint(-10, 10) for _ in range(size)) target random.randint(-10, 10) # 暴力找第一个/最后一个 expected_first -1 expected_last -1 for i, v in enumerate(nums): if v target and expected_first -1: expected_first i if v target: expected_last i assert first_position(nums, target) expected_first assert last_position(nums, target) expected_last print(all tests passed) verify()这种随机化测试非常适合在本地环境验证算法实现。它能覆盖大量边界组合比手写几个测试用例更让人放心。7. 二分查找的常见问题与排查思路把常见的错误归一下类方便你以后遇到问题时快速定位。问题现象可能原因排查方式解决方案程序卡住不退出while 循环陷入死循环检查区间收缩语句闭区间模板下使用left mid 1或right mid - 1下标越界IndexError数组为空、或 bisect 返回位置等于数组长度在访问nums[pos]前判断pos len(nums)先判断位置合法性再访问数组元素返回值比预期偏大或偏小对左边界和右边界的定义理解错误对照左右边界函数的收缩条件需要找第一个时用nums[mid] target收缩右边界需要找最后一个时用nums[mid] target收缩左边界结果为 -1但目标值实际存在循环退出条件写成了left right检查 while 条件闭区间模板使用while left right整数溢出问题其他语言mid (left right) // 2在极端值下相加溢出使用安全写法统一写成mid left (right - left) // 2这些错误几乎是所有二分查找初学者都会踩的。好在它们都有比较固定的排查路径先检查循环条件再检查区间收缩最后检查边界值。8. 二分查找的最佳实践与工程建议学习二分查找不能只停留在“会做几道题”的层面。在实际开发和后续学习中有一些习惯和原则值得养成。8.1 统一模板减少思考负担网上关于二分查找的写法五花八门有开区间写法、闭区间写法、左闭右开写法。不同的写法对应不同的边界条件经常切换会导致混乱。我的建议是选择一种自己最容易理解的模板比如本文使用的闭区间模板然后在所有题目中统一使用。只要区间定义、循环条件、收缩规则三者始终一致正确率会显著提高。具体来说闭区间模板的三个核心约定是left和right分别指向当前搜索区间的左右端点两个端点都包含在区间内while 条件为left right表示区间不为空时继续搜索收缩区间时必须排除已经比较过的mid即left mid 1或right mid - 1。只要这三个约定不变整个代码的结构就非常稳定。8.2 手写之前先想清楚要找的是什么在实际问题里“用什么条件收缩区间”取决于你要找的目标。找任意一个等于目标值的元素相等时直接返回。找第一个等于目标值的元素相等时不返回继续收缩右边界。找最后一个等于目标值的元素相等时不返回继续收缩左边界。找第一个大于等于目标值的元素这是bisect_left的语义。找第一个大于目标值的元素这是bisect_right的语义。先弄清楚自己在找什么再动手写代码比一上来就套模板靠谱得多。8.3 在项目中使用标准库优先如果只是在业务代码里维护有序列表建议优先使用bisect模块。它的实现经过充分测试语义清晰比手写代码更不容易出错。import bisect scores [60, 70, 80, 90, 90, 95] # 第一个大于等于 85 的位置 pos bisect.bisect_left(scores, 85) print(pos) # 3 # 插入一个分数并保持有序 bisect.insort(scores, 85) print(scores) # [60, 70, 80, 85, 90, 90, 95]当然bisect只能用于 list 等支持随机访问的序列并且要求序列始终有序。如果数据频繁插入删除可能需要考虑其他数据结构。8.4 边界测试永远不能省二分查找的 bug 往往不在正常路径上而在边界路径上。写完后至少测四组数据空数组只有一个元素的数组目标值在数组最前面目标值在数组最后面。这种测试成本很低但能帮你挡住绝大多数低级错误。8.5 理解二分思想而不只是背代码二分查找的思想本质是在单调有序的搜索空间中通过比较中间元素排除掉一半不可能的区域。这个思想可以扩展到很多场景比如在有序矩阵中查找、在旋转排序数组中查找最小值、求解浮点数方程的根等。如果只是背住了二分查找的模板遇到这些变体依然会手足无措。所以当你有余力时可以去找一些二分查找的进阶题目练习重点不是刷数量而是在每道题里找出“搜索空间是什么”“判断条件是什么”“如何排除一半区域”。9. 总结与下一步实践建议整理一下这篇文章的核心内容二分查找适用于有序数组中的快速查找时间复杂度为 O(log n)远优于线性查找的 O(n)。最基础的二分查找实现并不复杂关键在闭区间、循环条件和区间收缩三个约定上保持一致。重复元素场景下查找第一个等于目标值、最后一个等于目标值需要改写成边界收缩版本。Python 标准库bisect提供了现成的二分查找工具业务开发中优先使用它能减少手写带来的边界问题。二分查找最常见的坑是死循环、下标越界和边界值漏测建议写完代码后立刻用边界测试用例验证。下一步的实践建议也很明确在本地跑一遍本文的完整示例脚本确认所有输出符合预期。在不看代码的情况下自己手写一遍基础二分查找、左边界查找和右边界查找直到能一次写对。去 LeetCode 搜索标签为“二分查找”的题目从第 704 题开始然后做 34、35、744、278 等经典题。如果你在 PTA 或学校 OJ 上刷题遇到“二分查找满足条件的数”这类题目时试着用本文的边界收缩模板去写而不是靠猜。二分查找是一个“看似简单实则讲究”的算法。希望这篇文章能帮你把背后的逻辑彻底搞清楚而不是停留在背模板的层面。等你熟练之后你会发现它不仅是一个面试考点更是你分析问题、优化性能时的重要工具。 
如果你是一个 Python 初学者或者已经在写业务代码但很少接触算法我想先抛出一个很直接的观点二分查找不是一个“会背模板就行”的知识点而是一个值得反复练习、直到形成肌肉记忆的基础算法。很多人在学习二分查找时都有过这样的经历看教程时觉得很简单就是“三个变量、一个循环、不断缩小区间”可一旦自己动手写或者去 LeetCode、PTA 上做题就会遇到各种莫名其妙的问题——死循环、下标越界、查不到目标值、边界情况漏掉。更扎心的是代码看着和别人的一模一样运行结果却不对。这篇文章不会只给你一个模板。我会从头梳理二分查找的适用条件、核心逻辑、完整实现、常见变体以及 Python 标准库bisect的用法。每一步都讲清楚“为什么要这么写”而不是让你死记硬背。读完这篇文章你应该能达成三个目标不用查资料写出正确的二分查找代码能够处理“查找第一个等于目标值的元素”“查找最后一个等于目标值的元素”这类变体问题在实际项目里知道什么时候应该自己手写什么时候应该直接使用bisect模块。1. 二分查找到底解决了什么问题在进入代码之前先说说二分查找的定位。二分查找也叫折半查找是一种在有序数组中查找特定元素的高效算法。它的核心思想是每次把待查找的区间缩小一半通过比较中间元素与目标值的大小关系决定下一步是向左半边继续查找还是向右半边继续查找。这个算法解决的最核心问题是在大规模有序数据中快速定位目标值。举个例子。假设你有一个长度为 100 万的已排序列表需要判断某一个数字是否存在。最直接的做法是遍历整个列表最坏情况下要比较 100 万次。如果使用二分查找最多只需要比较 20 次左右。这个差距在数据量越大时越明显。很多人可能会说现在机器性能这么强100 万次比较算什么但真实场景远没有这么简单。你需要考虑的是如果这个列表有 1 亿条数据呢如果这个查找操作在一秒钟内被调用成千上万次呢如果数据不是存在内存里而是需要查询远程数据库或外部存储呢在这些场景下O(n) 和 O(log n) 的差距就不是“快一点”的问题而是“能不能扛得住”的问题。所以二分查找看似是一个基础算法但它的思想渗透在很多底层系统和工具中数据库的索引查找、操作系统的文件系统分配、Git 的二分调试、各种数值计算库中的求根算法都能看到二分思想的影子。这也是为什么很多面试和笔试环节会专门考察二分查找——它不只是考你会不会写循环而是考察你能否处理边界、维护区间不变量、分析复杂度。1.1 暴力查找 vs 二分查找在没有学习二分查找之前大部分人查找元素的写法是这样的def find(nums, target): for i in range(len(nums)): if nums[i] target: return i return -1这种线性查找有两个特点代码简单不需要任何前置条件时间复杂度是 O(n)数据量大了以后性能直线下降。二分查找则有两个严格的前置条件数据必须存储在支持随机访问的结构中比如 Python 的list。链表不行因为无法直接通过下标访问中间元素。数据必须是有序的。这里的“有序”可以是升序也可以是降序但必须有一个确定的比较规则。我把两者的对比整理成下表对比维度线性查找二分查找前置条件无序、有序都可以必须有序且支持随机访问时间复杂度O(n)O(log n)代码复杂度极低中等需要注意边界适用数据量小规模数据中大规模数据常见实现方式for 循环遍历while 循环 区间收缩一个常见的误解是“二分查找只能用于数组”。实际上只要数据结构支持通过下标快速访问元素且元素之间可以比较大小二分查找的思想都可以应用。Python 的list、tuple、array都可以。1.2 为什么二分查找的时间复杂度是 O(log n)这个结论不需要死记理解推导过程就够了。假设数组长度为 n。第一次比较后如果没有找到目标值搜索范围缩小到 n/2第二次比较后缩小到 n/4第三次是 n/8……以此类推。最坏情况下我们需要一直缩小范围直到区间里只剩下一个元素。这个过程经过 k 次比较后区间大小变为 n / 2^k。当 n / 2^k 1 时也就是 2^k n解得 k log2(n)。因此在最坏情况下二分查找最多需要 log2(n) 1 次比较。在大 O 表示法中我们省略底数和常数记作 O(log n)。这个复杂度意味着什么当 n 10 亿时log2(n) 大约为 30。也就是说哪怕数据量到了十亿级别二分查找也只需要 30 次左右的比较就能定位到目标值。这也是它能在很多高性能系统中被广泛使用的原因。2. 手写第一个二分查找从最简版本开始现在进入实操环节。我们先从最经典的场景开始在一个升序排列的数组中查找目标值返回下标如果不存在返回 -1。这是 LeetCode 704 题、PTA 等平台的基础题型也是很多面试手写算法时的第一问。它的代码看起来很简单但隐藏了不少值得反复确认的细节。2.1 最简实现def binary_search(nums, target): left 0 right 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 0right len(nums) - 1。这里使用的是闭区间[left, right]也就是说目标值可能在区间内的任意一个位置包括left和right本身。第二while 循环的退出条件。while left right表示只要区间还没有被收缩到空集就继续查找。这里为什么用而不是因为当left right时区间里还有一个元素这个元素还没有被比较过不能退出循环。第三中间位置的计算。mid left (right - left) // 2。有些同学可能会写成mid (left right) // 2。两者在大多数情况下结果一样但前者更安全。为什么因为当left和right都是很大的整数时left right可能超出语言所能表示的整数上限导致溢出。虽然 Python 的整数不会溢出但这个习惯在 C、Java 等语言中非常重要。从写代码的第一天就养成好习惯没有坏处。第四区间收缩规则。当nums[mid] target时说明目标值在 mid 的右侧所以把左边界收缩到mid 1当nums[mid] target时说明目标值在 mid 的左侧所以把右边界收缩到mid - 1。这里特别需要注意的是收缩时要把mid排除在外而不是直接赋值为mid。否则如果目标值不存在循环可能永远无法退出。2.2 为什么一定可以终止每次循环区间要么缩小到左半部分要么缩小到右半部分并且都是从[left, right]变成[left, mid - 1]或[mid 1, right]。因为mid始终位于区间内部所以无论走哪个分支新区间的长度都严格小于旧区间的长度。这就保证了循环一定会结束。反过来如果某段代码把left mid或right mid那么当区间长度缩小到 1 时mid left right新的区间和旧区间完全一样就会陷入死循环。这是一个非常经典的二分查找 bug后面会详细展开。2.3 验证一下我们可以用一组简单的测试数据来验证上面的代码nums [1, 3, 5, 7, 9, 11, 13] target 7 print(binary_search(nums, target))预期输出为3因为nums[3]的值正好是 7。再测一个不存在的情况print(binary_search(nums, 8))预期输出为-1这个最简单的版本已经能覆盖大多数“判断一个数在不在有序数组里”的需求。但实际场景中我们经常会遇到更复杂的情况比如数组里有重复元素需要找到第一个等于目标值的位置或者最后一个等于目标值的位置。这就引出了二分查找的变体问题。3. 高频变体查找第一个等于目标和最后一个等于目标先看一个实际场景。假设你有一个学生的成绩列表已经按分数升序排列里面有很多重复分数。现在需要找到第一个等于 90 分的位置或者最后一个等于 90 分的位置。如果用最基础的二分查找因为nums[mid] target时就直接return mid你只会返回任意一个等于目标值的位置无法保证是第一个或最后一个。面试中经常考察的“二分查找左边界/右边界”问题就是在这个背景下提出的。3.1 查找第一个等于目标值的位置思路是即使找到了等于target的元素也不立刻返回而是继续把右边界向左收缩直到区间为空。这样最后一次满足nums[mid] target的位置就是最左边的那个。def first_position(nums, target): left 0 right len(nums) - 1 ans -1 while left right: mid left (right - left) // 2 if nums[mid] target: if nums[mid] target: ans mid right mid - 1 else: left mid 1 return ans这里的关键变化是当nums[mid] target时都往左半区继续找。等于的情况用ans记录下来然后继续向左压缩看左边还有没有相等的元素。如果左边没有相等的元素了最后一次记录的ans就是第一个等于目标值的位置。如果整个数组里没有目标值ans会一直保持-1最后返回-1。3.2 查找最后一个等于目标值的位置思路对称找到等于target的元素后不立刻返回而是继续把左边界向右收缩。def last_position(nums, target): left 0 right len(nums) - 1 ans -1 while left right: mid left (right - left) // 2 if nums[mid] target: if nums[mid] target: ans mid left mid 1 else: right mid - 1 return ans这里的核心变化是当nums[mid] target时都往右半区继续找。等于的情况记录到ans然后继续向右压缩确保最终记录的是右边的最后一个。3.3 变体问题为什么重要直接回答这个问题变体问题是区分“背模板”和“真理解”的分水岭。如果你只会最基础的版本遇到“查找第一个大于等于目标值的元素”“查找最后一个小于目标值的元素”“插入位置”等新题时就会不知所措。而只要你理解了“区间收缩”的本质——什么时候收缩左边界什么时候收缩右边界什么时候记录答案——你就能把二分查找迁移到任何边界查询问题上。在 Python 的实际项目中这类变体逻辑通常不需要你手写因为标准库bisect已经提供了现成的方法。但理解实现原理能帮助你判断应该调用bisect_left还是bisect_right以及如何结合返回值判断目标值是否存在。4. 用 Python 标准库 bisect 完成二分查找Python 的bisect模块提供了一套基于二分查找的实用函数常用于在有序列表中查找插入位置、定位左右边界等场景。很多 Python 开发者知道这个模块存在但实际使用频率并不高。这其实很可惜因为bisect不仅代码简洁性能还非常可靠。4.1 bisect 的常用函数bisect模块中最常用的两个函数是bisect_left和bisect_right。bisect_left(a, x)返回将x插入到有序列表a中的最左侧位置使得插入后列表仍然有序。如果a中存在等于x的元素返回的是第一个等于x的元素的下标。bisect_right(a, x)返回将x插入到有序列表a中的最右侧位置。如果a中存在等于x的元素返回的是最后一个等于x的元素下标加一。来看一个简单例子import bisect nums [1, 3, 3, 5, 7, 9] print(bisect.bisect_left(nums, 3)) # 输出 1 print(bisect.bisect_right(nums, 3)) # 输出 3这里bisect_left返回 1说明第一个等于 3 的位置下标是 1bisect_right返回 3说明最后一个等于 3 的位置下标是 2加一后是 3。4.2 用 bisect 实现“查找目标值是否存在”import bisect def binary_search(nums, target): pos bisect.bisect_left(nums, target) if pos len(nums) and nums[pos] target: return pos return -1 nums [1, 3, 5, 7, 9] print(binary_search(nums, 7)) # 输出 3 print(binary_search(nums, 8)) # 输出 -1这里有一个细节需要注意bisect_left返回的位置有可能是数组长度len(nums)表示目标值比数组中所有元素都大插入位置在末尾。因此在判断nums[pos] target之前必须先检查pos len(nums)否则会触发下标越界。4.3 bisect 在“插入元素保持有序”场景中的使用假设你维护了一个有序列表需要频繁插入新元素同时保持列表有序。最粗暴的方式是列表追加后再排序但时间复杂度较高。使用bisect可以精确定位插入位置import bisect nums [1, 3, 5, 7, 9] bisect.insort(nums, 4) print(nums) # 输出 [1, 3, 4, 5, 7, 9]insort函数会先调用bisect_left或bisect_right找到插入位置然后在对应位置执行插入操作。注意列表插入操作本身是 O(n) 的因为需要移动后续元素bisect只解决了“找到插入位置”这一部分的 O(log n)整体性能依然受制于列表结构。如果插入非常频繁应该考虑使用heapq堆或sortedcontainers等更合适的数据结构。4.4 什么时候选择手写什么时候选择 bisect这是一个非常实际的问题。我的建议是如果你只是需要在有序列表里快速定位插入位置或者查找左右边界直接用bisect不需要手写。如果你是学习算法或者面试手写代码必须让自己熟练手写二分查找。如果你的查找逻辑不是标准的“等于、第一个等于、最后一个等于”而是更复杂的条件比如“查找第一个满足某个自定义谓词的元素”使用bisect可能不太方便手写会更灵活。5. 二分查找最常见的坑死循环与下标越界二分查找之所以被称为“思路简单但实现容易出错”的算法是因为它有一些隐蔽的边界问题。即使是有多年经验的开发者偶尔也会在细节上翻车。下面列出几个最常见的坑并分析原因。5.1 死循环死循环通常是区间收缩写错导致的。最典型的情况是left mid或right mid。看一个错误示例def wrong_binary_search(nums, target): left 0 right len(nums) - 1 while left right: mid (left right) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid # 错误应该写成 mid 1 else: right mid # 错误应该写成 mid - 1 return -1当区间缩小到[left, right]且nums[mid]不等于目标值时如果left mid而 mid 恰好等于 left那么新区间和旧区间完全相同循环无法退出最终形成死循环。解决办法是在闭区间[left, right]的模板中收缩时必须排除掉已经比较过的mid也就是left mid 1或right mid - 1。5.2 下标越界下标越界通常发生在以下两种情况。第一种数组为空时直接访问nums[mid]。比如传入nums []right -1while left right的条件不成立循环根本不执行所以不会越界。但如果代码里在进入 while 之前就访问nums[0]就会越界。第二种使用了bisect_left或bisect_right之后没有判断返回位置是否等于len(nums)就访问nums[pos]。前面已经强调过bisect_left返回的位置可能等于数组长度此时nums[pos]会触发IndexError。5.3 取中间值时溢出在 C 或 Java 中(left right) // 2在left right超过整数上限时会产生溢出。虽然 Python 整数没有这个问题但在阅读其他语言代码或手写算法时很多人会下意识用这种方式。为了避免坏习惯建议统一写成left (right - left) // 2。5.4 忘记思考空数组和单元素数组二分查找的边界测试中空数组和单元素数组是最高频的出错点。写完之后建议至少跑一遍这两种输入print(binary_search([], 5)) # 应该输出 -1 print(binary_search([5], 5)) # 应该输出 0 print(binary_search([5], 3)) # 应该输出 -1很多看起来没问题的代码在这三组测试上会现出原形。6. 完整示例一个可直接运行的 Python 脚本把上面的内容串起来写一个包含基础二分查找、左右边界查找、bisect 用法的完整 Python 脚本。你可以直接把代码复制到本地运行。# -*- coding: utf-8 -*- 二分查找有序数组 示例脚本 运行环境Python 3.6 import bisect def binary_search(nums, target): 在有序数组 nums 中查找 target返回下标不存在返回 -1。 left 0 right 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 def first_position(nums, target): 返回第一个等于 target 的下标不存在返回 -1。 left 0 right len(nums) - 1 ans -1 while left right: mid left (right - left) // 2 if nums[mid] target: if nums[mid] target: ans mid right mid - 1 else: left mid 1 return ans def last_position(nums, target): 返回最后一个等于 target 的下标不存在返回 -1。 left 0 right len(nums) - 1 ans -1 while left right: mid left (right - left) // 2 if nums[mid] target: if nums[mid] target: ans mid left mid 1 else: right mid - 1 return ans def bisect_search(nums, target): 使用 bisect 模块实现查找。 pos bisect.bisect_left(nums, target) if pos len(nums) and nums[pos] target: return pos return -1 if __name__ __main__: test_data [1, 3, 3, 5, 7, 9, 9, 11] print(基础二分查找) print(binary_search(test_data, 7)) # 4 print(binary_search(test_data, 8)) # -1 print(第一个等于目标值) print(first_position(test_data, 3)) # 1 print(first_position(test_data, 9)) # 5 print(first_position(test_data, 10)) # -1 print(最后一个等于目标值) print(last_position(test_data, 3)) # 2 print(last_position(test_data, 9)) # 6 print(last_position(test_data, 10)) # -1 print(bisect 模块查找) print(bisect_search(test_data, 7)) # 4 print(bisect_search(test_data, 8)) # -1 print(边界测试) print(binary_search([], 5)) # -1 print(binary_search([5], 5)) # 0 print(binary_search([5], 3)) # -1运行这个脚本正常的输出应该是基础二分查找 4 -1 第一个等于目标值 1 5 -1 最后一个等于目标值 2 6 -1 bisect 模块查找 4 -1 边界测试 -1 0 -1如果你得到的输出和这里不一致说明某个函数实现有问题可以对照前面的代码逐行检查。6.1 如何验证代码的正确性除了手动测试还可以用更系统的方式验证生成一个随机有序数组再暴力遍历确认每个函数的结果是否正确。import random def verify(): for _ in range(1000): size random.randint(0, 30) nums sorted(random.randint(-10, 10) for _ in range(size)) target random.randint(-10, 10) # 暴力找第一个/最后一个 expected_first -1 expected_last -1 for i, v in enumerate(nums): if v target and expected_first -1: expected_first i if v target: expected_last i assert first_position(nums, target) expected_first assert last_position(nums, target) expected_last print(all tests passed) verify()这种随机化测试非常适合在本地环境验证算法实现。它能覆盖大量边界组合比手写几个测试用例更让人放心。7. 二分查找的常见问题与排查思路把常见的错误归一下类方便你以后遇到问题时快速定位。问题现象可能原因排查方式解决方案程序卡住不退出while 循环陷入死循环检查区间收缩语句闭区间模板下使用left mid 1或right mid - 1下标越界IndexError数组为空、或 bisect 返回位置等于数组长度在访问nums[pos]前判断pos len(nums)先判断位置合法性再访问数组元素返回值比预期偏大或偏小对左边界和右边界的定义理解错误对照左右边界函数的收缩条件需要找第一个时用nums[mid] target收缩右边界需要找最后一个时用nums[mid] target收缩左边界结果为 -1但目标值实际存在循环退出条件写成了left right检查 while 条件闭区间模板使用while left right整数溢出问题其他语言mid (left right) // 2在极端值下相加溢出使用安全写法统一写成mid left (right - left) // 2这些错误几乎是所有二分查找初学者都会踩的。好在它们都有比较固定的排查路径先检查循环条件再检查区间收缩最后检查边界值。8. 二分查找的最佳实践与工程建议学习二分查找不能只停留在“会做几道题”的层面。在实际开发和后续学习中有一些习惯和原则值得养成。8.1 统一模板减少思考负担网上关于二分查找的写法五花八门有开区间写法、闭区间写法、左闭右开写法。不同的写法对应不同的边界条件经常切换会导致混乱。我的建议是选择一种自己最容易理解的模板比如本文使用的闭区间模板然后在所有题目中统一使用。只要区间定义、循环条件、收缩规则三者始终一致正确率会显著提高。具体来说闭区间模板的三个核心约定是left和right分别指向当前搜索区间的左右端点两个端点都包含在区间内while 条件为left right表示区间不为空时继续搜索收缩区间时必须排除已经比较过的mid即left mid 1或right mid - 1。只要这三个约定不变整个代码的结构就非常稳定。8.2 手写之前先想清楚要找的是什么在实际问题里“用什么条件收缩区间”取决于你要找的目标。找任意一个等于目标值的元素相等时直接返回。找第一个等于目标值的元素相等时不返回继续收缩右边界。找最后一个等于目标值的元素相等时不返回继续收缩左边界。找第一个大于等于目标值的元素这是bisect_left的语义。找第一个大于目标值的元素这是bisect_right的语义。先弄清楚自己在找什么再动手写代码比一上来就套模板靠谱得多。8.3 在项目中使用标准库优先如果只是在业务代码里维护有序列表建议优先使用bisect模块。它的实现经过充分测试语义清晰比手写代码更不容易出错。import bisect scores [60, 70, 80, 90, 90, 95] # 第一个大于等于 85 的位置 pos bisect.bisect_left(scores, 85) print(pos) # 3 # 插入一个分数并保持有序 bisect.insort(scores, 85) print(scores) # [60, 70, 80, 85, 90, 90, 95]当然bisect只能用于 list 等支持随机访问的序列并且要求序列始终有序。如果数据频繁插入删除可能需要考虑其他数据结构。8.4 边界测试永远不能省二分查找的 bug 往往不在正常路径上而在边界路径上。写完后至少测四组数据空数组只有一个元素的数组目标值在数组最前面目标值在数组最后面。这种测试成本很低但能帮你挡住绝大多数低级错误。8.5 理解二分思想而不只是背代码二分查找的思想本质是在单调有序的搜索空间中通过比较中间元素排除掉一半不可能的区域。这个思想可以扩展到很多场景比如在有序矩阵中查找、在旋转排序数组中查找最小值、求解浮点数方程的根等。如果只是背住了二分查找的模板遇到这些变体依然会手足无措。所以当你有余力时可以去找一些二分查找的进阶题目练习重点不是刷数量而是在每道题里找出“搜索空间是什么”“判断条件是什么”“如何排除一半区域”。9. 总结与下一步实践建议整理一下这篇文章的核心内容二分查找适用于有序数组中的快速查找时间复杂度为 O(log n)远优于线性查找的 O(n)。最基础的二分查找实现并不复杂关键在闭区间、循环条件和区间收缩三个约定上保持一致。重复元素场景下查找第一个等于目标值、最后一个等于目标值需要改写成边界收缩版本。Python 标准库bisect提供了现成的二分查找工具业务开发中优先使用它能减少手写带来的边界问题。二分查找最常见的坑是死循环、下标越界和边界值漏测建议写完代码后立刻用边界测试用例验证。下一步的实践建议也很明确在本地跑一遍本文的完整示例脚本确认所有输出符合预期。在不看代码的情况下自己手写一遍基础二分查找、左边界查找和右边界查找直到能一次写对。去 LeetCode 搜索标签为“二分查找”的题目从第 704 题开始然后做 34、35、744、278 等经典题。如果你在 PTA 或学校 OJ 上刷题遇到“二分查找满足条件的数”这类题目时试着用本文的边界收缩模板去写而不是靠猜。二分查找是一个“看似简单实则讲究”的算法。希望这篇文章能帮你把背后的逻辑彻底搞清楚而不是停留在背模板的层面。等你熟练之后你会发现它不仅是一个面试考点更是你分析问题、优化性能时的重要工具。