1. 从一道面试题说起为什么二分查找总在边界翻车先抛个场景。面试官让你手写二分查找你心想这不送分题吗五分钟写完了结果跑测试用例时在nums [1, 2, 3]这种只有三个元素的数组上直接死循环或者返回了错误的插入位置。这种情况我见过的次数多到可以开班。别看二分查找代码就十几行它却是算法面试里翻车率最高的基础题。核心关键词“算法”也好“二分查找算法”也好大家都会背“有序数组、每次折半、O(log n)”但真正落到代码层面左右开闭区间怎么选、while 里写还是、mid要不要1每一个决策点都是坑。这篇文章就用工程和面试双重视角把二分查找从原理到边界、从模板到变种彻底拆一遍适合正在刷题准备面试的读者也适合工作中需要手写查找逻辑、但不想每次都被边界条件折磨的开发同学。我在实际项目里用二分查找写过配置版本回退、日志时间戳定位、数值区间匹配踩过的坑比刷题时还多。因为业务里的边界条件往往更诡异不是单调递增的干净数组而是带重复、带缺失、甚至带业务含义的区间判断。所以要真理解二分查找绝不能停留在“背模板”的层面。2. 二分查找的设计思路为什么是 O(log n)以及三个关键选择2.1 折半搜索的数学直觉二分查找的底层逻辑非常朴素在有序序列中每次比较中间元素如果目标值小于中间值就砍掉右半边反之砍掉左半边直到找到目标或区间为空。这个过程的复杂度为什么是 O(log n)因为每轮比较后待搜索的区间长度减半。假设数组长度是 n经过 k 轮后区间长度为 n / 2^k当这个值小于 1 时搜索结束即 n / 2^k 1解得 k log2(n)。所以一百万的数据量最多只需要二十次比较这就是二分查找在工程中被广泛使用的根本原因。大 O 记法描述的是增长趋势。二分查找每次操作是常数时间比较循环次数是 log2(n) 级别所以总体是 O(log n)。这个复杂度介于 O(1) 和 O(n) 之间在很多实时性要求高的场景里是“既快又简单”的典型方案。2.2 三个影响成败的设计决策写二分查找前必须想清楚三个问题这三个问题决定了你用哪种模板也决定了代码对不对。第一个是区间定义。左闭右闭[left, right]意味着 left 和 right 都可能是有效索引左闭右开[left, right)意味着 right 是边界但不参与比较。两种定义对应的初始化、while 条件、收缩方式都不一样。混用是新手最常见的错误源。第二个是 while 条件。区间定义决定条件是left right还是left right。闭区间下两者都可以用但更通用能覆盖区间只剩一个元素的情况开区间下必须用因为left right时区间已经为空。第三个是mid的计算与收缩逻辑。经典写法是int mid left (right - left) / 2注意用减法替代(left right) / 2能避免两个大整数相加溢出。收缩时如果目标在左半边则right mid - 1闭区间或right mid开区间在右半边则left mid 1。这里最容易出死循环的位置是left mid而不是left mid 1一旦 mid 收敛到与 left 相同就会永远跳不出去。2.3 为什么标准库和成熟框架都用“右开区间”很多语言的标准库比如 C 的 STL、Python 的 bisect都默认使用左闭右开区间[begin, end)。这背后有数学和工程上的双重原因。从数学角度看半开区间[begin, end)能天然表达“空容器”的概念begin 等于 end 时为空。而且迭代器语义里end 指代“最后一个元素的下一个位置”对应循环遍历的惯用法。从工程角度看半开区间长度直接用end - begin计算无需加一减一配合mid begin (end - begin) / 2非常工整不容易出错。所以学习二分查找时我强烈建议先掌握左闭右闭版本理解透彻后再切换到左闭右开因为很多面试追问和源码阅读都需要你快速理解半开区间的写法。3. 三种二分查找模板与实操要点3.1 模板一标准左闭右闭查找这是最直观、最适合入门的版本。代码逻辑是在[left, right]区间内查找目标值找到返回索引找不到返回 -1。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关键点有三个。初始化时right len(nums) - 1因为闭区间包含最后一个元素。while 用这样当区间只剩一个元素时还能进入循环判断。收缩时left mid 1、right mid - 1保证每次循环区间至少缩小一个元素不会死循环。这个模板的优点是简单清晰适合在面试中快速写出可运行的代码。缺点是在处理“查找左边界”“查找右边界”这类变种时需要额外记一套逻辑容易混淆。3.2 模板二左闭右开查找这个版本贴合标准库风格也是我工作中最常用的。代码把区间定义成[left, right)right 本身不包括在搜索范围内。def binary_search(nums, target): left, right 0, len(nums) # 注意 right 是 len(nums)不是 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 return -1这里的核心差异是当nums[mid] target时right mid因为右开区间不包含 right直接把 right 收缩到 mid 是安全的。而nums[mid] target时left mid 1因为 mid 已经比较过可以排除。while 条件必须用因为在开区间下left right意味着区间为空。初始化right len(nums)也正是右开区间的标准写法允许索引越界作为终止标志。这个模板写多了会觉得比闭区间版本更顺手尤其在处理“查找第一个大于等于目标值的位置”这类问题时右开区间不会让你纠结于边界索引的加减一。3.3 模板三统一查找左右边界的变体面试里真正拉分的不是简单查找而是查找重复元素中的左边界或右边界也就是“第一个等于 target 的位置”和“最后一个等于 target 的位置”。这里我给出两个基于左闭右开的变体模板。# 查找第一个等于 target 的位置不存在返回 -1 def find_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 # 退出循环后 left 指向第一个 target 的位置 if left len(nums) and nums[left] target: return left return -1 # 查找最后一个等于 target 的位置不存在返回 -1 def find_right(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 # 退出循环后 left 指向第一个 target 的位置 # 所以最后一个等于 target 的位置是 left - 1 if left 0 and nums[left - 1] target: return left - 1 return -1左边界模板的核心逻辑是当nums[mid] target时让right mid把右边界向左收缩同时不排除 mid 本身因为 mid 可能就是第一个等于 target 的元素。这样退出循环后left 天然指向第一个不小于 target 的位置。右边界模板则相反nums[mid] target时让left mid 1把左边界向右推进最后 left 指向第一个大于 target 的位置减一就是最后一个等于 target 的位置。这两个模板我建议直接背下来并且必须配套动手推导一次否则面试现场临时推导容易出错。3.4 模板选型建议我把三个模板的适用场景整理成表格方便对照选择。模板类型区间定义while 条件收缩逻辑适合场景标准查找左闭右闭left rightleft mid 1 / right mid - 1无重复元素查找确切位置左闭右开左闭右开left rightleft mid 1 / right mid标准库风格通用性强边界变体左闭右开left right同左闭右开按条件收缩查找重复元素的左右边界如果只打算背一个模板应对大部分场景我推荐左闭右开版本。它能覆盖标准查找和边界查找且与 C STL、Python bisect 的区间语义一致理解后写变种时不需要反复调整边界。4. 实战从有序数组到二维矩阵与浮点数4.1 经典场景在旋转有序数组中查找目标值这是二分查找的高频面试题也是从“背模板”到“真会二分”的分水岭。题目是一个原本升序的数组在某个未知位置被旋转比如[4, 5, 6, 7, 0, 1, 2]在这个数组中查找目标值。核心思路是每次 mid 将数组分成两半至少有一半是严格有序的。先判断左半部分是否有序即nums[left] nums[mid]如果是检查 target 是否落在左半部分范围内是则收缩 right否则收缩 left如果左半部分无序则右半部分必然有序同理处理。def search_rotated(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 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 的区间判断必须使用半开区间写法nums[left] target nums[mid]不要拆成两个独立条件否则边界容易漏掉。4.2 经典场景二维矩阵的二分查找很多读者问二维矩阵怎么二分。其实思路是先定位行再在行内二分。有几种常见矩阵形态我分别说下处理方式。第一种是“每行内部有序、每行的第一个元素大于上一行的最后一个元素”的完全有序矩阵。这种可以直接把二维展成一维用一维二分处理。行号为mid // n列号为mid % nn 是列数。def search_matrix(matrix, target): if not matrix or not matrix[0]: return False m, n len(matrix), len(matrix[0]) left, right 0, m * n - 1 while left right: mid left (right - left) // 2 val matrix[mid // n][mid % n] if val target: return True elif val target: left mid 1 else: right mid - 1 return False第二种是“每行内部有序但列之间没有严格递增关系”的矩阵。这种情况就不能简单展平了需要用更巧妙的算法比如从左下角开始搜索。不过这不是二分查找的核心范畴这里不展开了。第三种是“每行每列都各自递增”的杨氏矩阵。这种矩阵的效率最高搜索方式也是从左下角或右上角开始每次排除一行或一列复杂度 O(m n)。严格说它不是二分查找但面试中常被归在“查找”大类里值得了解。4.3 浮点数二分精确度控制是核心二分查找不只是用于整数数组。在数值计算和机器学习领域浮点数二分也是常用工具典型场景是求解方程的根、单调函数的零点。浮点数二分的难点在于终止条件不是left right因为浮点数无法精确比较相等。需要用精度控制当区间长度小于某个阈值时停止或者迭代固定次数。def sqrt_binary(x, epsilon1e-7): if x 0: raise ValueError(negative input) if x 1: left, right x, 1 else: left, right 0, x while right - left epsilon: mid left (right - left) / 2 if mid * mid x: left mid else: right mid return (left right) / 2注意这里left mid或right mid都没有加减一因为浮点数不存在“下一个整数索引”只需要把边界收敛到目标精度即可。我习惯设定一个合理的 epsilon比如 1e-7同时最多迭代 100 次兜底防止极端输入下死循环。4.4 实战心得不要把二分只用在“数组”上我参与过一个配置系统需要根据时间戳快速定位某个版本生效期间的自定义配置。第一反应是写个遍历但配置数量上百万后每次查询遍历太慢。后来把配置按生效时间戳排序用二分查找“最后一个小于等于查询时间戳的位置”查一次从几十毫秒降到微秒级。这个场景的本质是任何满足单调性质的数据集合都可以用二分查找加速。时间戳排序天然满足单调性数值区间、日志偏移量、版本号列表都适用。所以学二分查找别只盯着数组题想要建立“单调有序就二分”的直觉。5. 死循环、溢出与边界场景问题排查实录5.1 经典死循环场景“mid 不前进”最典型的死循环发生在重复查找右边界时如果写成left mid而不是left mid 1当区间只剩两个元素时mid 恒等于 left导致 left 永远无法逼近 right。举例nums [1, 2, 2, 2, 3]target 2查找右边界。假设某轮left 1、right 2mid 1nums[mid] target满足条件如果执行left mid则 left 仍然是 1区间没有缩小下一次循环还是同样结果。解决方案在“需要保留 mid 作为候选”的情况下使用left mid 1或right mid来保证收缩如果实在需要left mid在循环体内加一个“若 mid left 则 break”的兜底逻辑但这样不优雅容易掩盖问题。5.2 整数溢出为什么要用减法求 mid(left right) // 2在 left 和 right 都很大时会溢出Java 和 C 的 int 溢出后变成负数直接导致 mid 指向错误位置。这是经典面试考点。正确写法是mid left (right - left) // 2。这个公式的数学含义是先算出区间长度的一半再加到 left 上结果与(left right) // 2相同但避免了加法溢出。在 Python 中整数不会溢出但养成这个习惯没有坏处因为你在面试时可能写的是 Java 或 C。我建议所有语言的二分查找实现都统一使用这个写法。5.3 边界场景空数组、单个元素、目标不存在、重复元素我整理了一份边界场景自查表每次写完二分查找代码按这张表过一遍基本能覆盖 90% 的问题。场景期望行为易错点空数组[]返回 -1 或指定位置初始化 left 0, right -1 时while 条件直接不满足返回 -1 是自然的单元素数组[x]如果 x target 返回 0否则 -1左闭右闭用 才能进入循环左闭右开用 也能进入目标在数组开头返回 0 或第一个匹配位置收缩逻辑必须允许 left 收缩到 0目标在数组末尾返回 len - 1 或最后一个匹配位置right 的收缩不能把最后一个元素排除掉目标不存在返回 -1或返回“应该插入的位置”插入位置场景需要理解 left 的最终含义全部重复元素返回左边界或右边界需要清楚自己写的是左边界还是右边界模板我实际刷题时发现许多人在“目标不存在”这一场景栽跟头。如果不清楚退出循环后 left 和 right 的含义就不知道应该返回插入位置还是 -1。这里有个通用结论在左闭右开模板下退出循环后 left 指向“第一个不小于 target 的位置”这个位置就是应该插入的位置。5.4 排查实战拿日志帮你看清循环过程如果代码异常但看不出原因我推荐一个调试技巧在循环体内打印 left、right、mid 三者的值跑几个小例子观察变化。以死循环为例打印后你会立刻看到left一直没有变化或mid一直等于left定位到问题就快多了。我写过不少次一开始也觉得打印日志太基础浪费时间但真到了复杂变种题里纸面推演和实际打印验证的差距很大。尤其是面试现场时间紧迫能快速用简单用例定位边界问题比硬推十行代码高效得多。6. 二分查找的进阶从“查找”到“答案”6.1 二分答案单调函数求极值二分查找的高级玩法是“二分答案”。核心思想是问题的答案是一个连续或离散的数值且这个数值具有单调性那么可以用二分搜答案空间代替直接求解。举一个经典例子给定一段木材的长度数组和一个目标段数 k问能切出的最大等长段长度是多少。暴力做法是从大到小枚举长度复杂度 O(n * max_len)。二分答案的做法是在长度空间[0, max_len]上二分每次判断当前长度能否切出 k 段判断是 O(n)总复杂度 O(n * log(max_len))。在机器学习相关的算法设计中这类思路也常见。比如找一个学习率区间的最优边界、找某个阈值使正负样本分割效果最优本质都是“在单调空间上求边界”二分答案的思想能直接迁移。6.2 二分查找与数据结构结合二分查找和数据结构结合的场景也很多。比如树状数组上二分查找前缀和位置用来解决“查找第 k 个大于某个值的元素”之类的问题再比如平衡树中的二分本质是在树上做类似的比较查找。这些进阶内容对面试和工程都有价值但绝不是基础学习阶段该碰的。先把一维数组的二分写到条件反射级别再去研究数据结构上的变体才比较稳妥。6.3 一个完整的二分答案实操案例我用一个业务场景来演示二分答案的实操过程。假设系统里有大量任务每个任务有独立的执行时长你希望把任务分配给 n 个 worker每个 worker 在单位时间内只能执行一个任务问完成所有任务的最短时间。这个问题用二分答案非常自然。def can_finish(tasks, workers, time_limit): # 判断在 time_limit 时间内 workers 个 worker 能否完成所有任务 count 0 for t in tasks: count (t time_limit - 1) // time_limit return count workers def min_time_to_finish(tasks, workers): left, right 1, max(tasks) while left right: mid left (right - left) // 2 if can_finish(tasks, workers, mid): right mid else: left mid 1 return left这个例子里can_finish就是单调函数时间越长越容易完成所有任务。二分搜最小时间每次判断时检查是否能完成左边能完成就收缩右边界不能完成就推进左边界最终 left 就是最短完成时间。这类问题在实际的需求排期、资源分配里经常遇到只是很多人没有意识到可以用二分答案来优雅处理。7. 语言差异与标准库使用杂谈7.1 Python 的 bisect 模块Python 标准库提供了 bisect 模块封装了二分查找的核心操作。它有bisect_left和bisect_right两个函数分别对应查找左边界和右边界。实际使用时bisect_left(a, x)返回第一个大于等于 x 的插入位置bisect_right(a, x)返回第一个大于 x 的插入位置。使用它的好处是效率高且不会有边界错误但代价是你必须理解返回值的含义。很多新手调用bisect_left后还要手动判断返回位置的值是否等于 target才能确定是否真的存在目标值。如果你已经熟练掌握了前面教的左闭右开模板那么 bisect 模块的返回值对你来说就是顺理成章的不需要额外记。7.2 C STL 的 lower_bound 与 upper_boundC 的algorithm库提供了lower_bound和upper_bound语义与 Python bisect 一致。前者返回第一个不小于 target 的迭代器后者返回第一个大于 target 的迭代器。两者相减就能得到数组中等于 target 的元素数量。STL 内部实现就是左闭右开区间的二分查找所以如果你能理解右开区间模板阅读 STL 源码时会非常顺畅。我在工作中写 C 时几乎不手写二分查找直接用 lower_bound但前提是理解它的行为否则遇到自定义比较器照样翻车。7.3 什么时候该手写二分虽然标准库很强大但有些场景必须手写需要在查找过程中同时记录额外信息比如比较次数、访问过的路径需要在非数组的数据结构上二分比如链表、文件偏移需要高度定制比较逻辑标准库接口不好表达面试或考核场景要求手写所以我建议标准库会用手写能力也要过关。两者不冲突反而相辅相成。理解手写本质后标准库用起来更自信熟练用标准库后写手写逻辑时也更清楚自己在干什么。8. 从零到一刷题路线与常见误区总结8.1 推荐的刷题顺序二分查找的题量不大但题型差异明显。我的建议是从最基础的查找开始按这个顺序刷第一梯队是标准二分查找在无重复有序数组中查找目标目标是不存在时返回 -1。这个题型一题就够关键是闭区间模板要滚瓜烂熟。第二梯队是查找左右边界数组中有重复元素要求分别返回第一个等于和最后一个等于 target 的位置。这个题型至少要刷三题因为实现细节不同容易混淆。第三梯队是二分答案比如切木头、爱吃香蕉的珂珂这类题目。重点在于怎么判断“答案是否可行”也就是写can_finish函数。第四梯队是变形题比如旋转有序数组、二维矩阵查找。这类题需要熟悉“部分有序”的判断方法。8.2 三个最高频误区第一个误区是把二分查找当成“只能查有序数组”。实际上只要数据具有单调性质无论是时间戳、得分、概率值都可以套二分模板。我见过有人面对“找到第一个满足某个复杂条件的位置”这类问题时毫无头绪其实题目只是换了一层业务皮核心还是二分。第二个误区是认为二分查找很简单所以不写测试用例。我自己踩过的坑写完模板自测一个正常数组通过了就以为没事。结果在单元素数组、空数组、目标在端点、重复元素这几个边界上全部翻车。后来我养成一个习惯每写一个二分相关函数先把这几个边界用例在脑子里过一遍或者直接在测试代码里跑一遍。第三个误区是过度优化。很多人喜欢在模板里写各种花式分支或者在循环里加特殊判断来提前退出。这些优化在面试中往往适得其反因为每加一个分支边界条件就多一层复杂度。二分查找本身 O(log n) 已经很快不要为了少一次循环把代码写到别人看不懂你自己三天后再看也看不懂。8.3 面试中的表达技巧面试时手写二分查找我建议按这个流程走先和面试官确认输入是否有序、是否有重复元素、返回要求是索引还是位置。这一步看似多余但能避免后续方向性错误。然后说明你的区间定义比如“我使用左闭右开区间”这能让面试官快速理解你的代码结构也显得你有逻辑。写完代码后自己举一个包含边界情况的例子走一遍比如[1, 2, 2, 4]target 分别是 0、2、5验证返回值是否符合预期。这个动作在面试中非常加分因为这显示了你会主动验证边界。最后如果面试官追问“还能怎么优化”可以提一下用位运算mid (left right) 1的写法但要说明这在语义上与除法等价并不是真正的优化重点。9. 写在最后的个人经验二分查找是算法里典型的“基础决定上层”的内容。我见过很多人花大量时间研究高级算法回头却在一道基础二分题上被卡住原因不是智商问题而是对边界条件的理解停留在“背模板”层面没有真正理解区间演变的逻辑。我个人在实际使用中的体会是把区间定义想清楚再动笔比写几十行代码重要得多。每次用之前花十秒钟问自己三个问题我用的是开区间还是闭区间while 条件是什么收缩时 mid 是否需要保留这三个问题想清楚了代码基本不会出错。最后再分享一个小技巧把二分查找模板记在脑子里之后不妨在平时的工作代码里刻意用一次。比如你需要在一个有序配置列表里查找某个阈值对应的配置项用二分替代遍历感受一下从十几毫秒到微秒级的速度变化。这种“学以致用”的成就感比刷一百道题都有用。这个内容后续还可以扩展到三分查找、二分图匹配、树上的二分等方向上但那是另一个话题了。先把基础的二分吃透后面的路自然会平坦很多。
二分查找算法详解：从边界条件到模板与实战应用
1. 从一道面试题说起为什么二分查找总在边界翻车先抛个场景。面试官让你手写二分查找你心想这不送分题吗五分钟写完了结果跑测试用例时在nums [1, 2, 3]这种只有三个元素的数组上直接死循环或者返回了错误的插入位置。这种情况我见过的次数多到可以开班。别看二分查找代码就十几行它却是算法面试里翻车率最高的基础题。核心关键词“算法”也好“二分查找算法”也好大家都会背“有序数组、每次折半、O(log n)”但真正落到代码层面左右开闭区间怎么选、while 里写还是、mid要不要1每一个决策点都是坑。这篇文章就用工程和面试双重视角把二分查找从原理到边界、从模板到变种彻底拆一遍适合正在刷题准备面试的读者也适合工作中需要手写查找逻辑、但不想每次都被边界条件折磨的开发同学。我在实际项目里用二分查找写过配置版本回退、日志时间戳定位、数值区间匹配踩过的坑比刷题时还多。因为业务里的边界条件往往更诡异不是单调递增的干净数组而是带重复、带缺失、甚至带业务含义的区间判断。所以要真理解二分查找绝不能停留在“背模板”的层面。2. 二分查找的设计思路为什么是 O(log n)以及三个关键选择2.1 折半搜索的数学直觉二分查找的底层逻辑非常朴素在有序序列中每次比较中间元素如果目标值小于中间值就砍掉右半边反之砍掉左半边直到找到目标或区间为空。这个过程的复杂度为什么是 O(log n)因为每轮比较后待搜索的区间长度减半。假设数组长度是 n经过 k 轮后区间长度为 n / 2^k当这个值小于 1 时搜索结束即 n / 2^k 1解得 k log2(n)。所以一百万的数据量最多只需要二十次比较这就是二分查找在工程中被广泛使用的根本原因。大 O 记法描述的是增长趋势。二分查找每次操作是常数时间比较循环次数是 log2(n) 级别所以总体是 O(log n)。这个复杂度介于 O(1) 和 O(n) 之间在很多实时性要求高的场景里是“既快又简单”的典型方案。2.2 三个影响成败的设计决策写二分查找前必须想清楚三个问题这三个问题决定了你用哪种模板也决定了代码对不对。第一个是区间定义。左闭右闭[left, right]意味着 left 和 right 都可能是有效索引左闭右开[left, right)意味着 right 是边界但不参与比较。两种定义对应的初始化、while 条件、收缩方式都不一样。混用是新手最常见的错误源。第二个是 while 条件。区间定义决定条件是left right还是left right。闭区间下两者都可以用但更通用能覆盖区间只剩一个元素的情况开区间下必须用因为left right时区间已经为空。第三个是mid的计算与收缩逻辑。经典写法是int mid left (right - left) / 2注意用减法替代(left right) / 2能避免两个大整数相加溢出。收缩时如果目标在左半边则right mid - 1闭区间或right mid开区间在右半边则left mid 1。这里最容易出死循环的位置是left mid而不是left mid 1一旦 mid 收敛到与 left 相同就会永远跳不出去。2.3 为什么标准库和成熟框架都用“右开区间”很多语言的标准库比如 C 的 STL、Python 的 bisect都默认使用左闭右开区间[begin, end)。这背后有数学和工程上的双重原因。从数学角度看半开区间[begin, end)能天然表达“空容器”的概念begin 等于 end 时为空。而且迭代器语义里end 指代“最后一个元素的下一个位置”对应循环遍历的惯用法。从工程角度看半开区间长度直接用end - begin计算无需加一减一配合mid begin (end - begin) / 2非常工整不容易出错。所以学习二分查找时我强烈建议先掌握左闭右闭版本理解透彻后再切换到左闭右开因为很多面试追问和源码阅读都需要你快速理解半开区间的写法。3. 三种二分查找模板与实操要点3.1 模板一标准左闭右闭查找这是最直观、最适合入门的版本。代码逻辑是在[left, right]区间内查找目标值找到返回索引找不到返回 -1。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关键点有三个。初始化时right len(nums) - 1因为闭区间包含最后一个元素。while 用这样当区间只剩一个元素时还能进入循环判断。收缩时left mid 1、right mid - 1保证每次循环区间至少缩小一个元素不会死循环。这个模板的优点是简单清晰适合在面试中快速写出可运行的代码。缺点是在处理“查找左边界”“查找右边界”这类变种时需要额外记一套逻辑容易混淆。3.2 模板二左闭右开查找这个版本贴合标准库风格也是我工作中最常用的。代码把区间定义成[left, right)right 本身不包括在搜索范围内。def binary_search(nums, target): left, right 0, len(nums) # 注意 right 是 len(nums)不是 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 return -1这里的核心差异是当nums[mid] target时right mid因为右开区间不包含 right直接把 right 收缩到 mid 是安全的。而nums[mid] target时left mid 1因为 mid 已经比较过可以排除。while 条件必须用因为在开区间下left right意味着区间为空。初始化right len(nums)也正是右开区间的标准写法允许索引越界作为终止标志。这个模板写多了会觉得比闭区间版本更顺手尤其在处理“查找第一个大于等于目标值的位置”这类问题时右开区间不会让你纠结于边界索引的加减一。3.3 模板三统一查找左右边界的变体面试里真正拉分的不是简单查找而是查找重复元素中的左边界或右边界也就是“第一个等于 target 的位置”和“最后一个等于 target 的位置”。这里我给出两个基于左闭右开的变体模板。# 查找第一个等于 target 的位置不存在返回 -1 def find_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 # 退出循环后 left 指向第一个 target 的位置 if left len(nums) and nums[left] target: return left return -1 # 查找最后一个等于 target 的位置不存在返回 -1 def find_right(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 # 退出循环后 left 指向第一个 target 的位置 # 所以最后一个等于 target 的位置是 left - 1 if left 0 and nums[left - 1] target: return left - 1 return -1左边界模板的核心逻辑是当nums[mid] target时让right mid把右边界向左收缩同时不排除 mid 本身因为 mid 可能就是第一个等于 target 的元素。这样退出循环后left 天然指向第一个不小于 target 的位置。右边界模板则相反nums[mid] target时让left mid 1把左边界向右推进最后 left 指向第一个大于 target 的位置减一就是最后一个等于 target 的位置。这两个模板我建议直接背下来并且必须配套动手推导一次否则面试现场临时推导容易出错。3.4 模板选型建议我把三个模板的适用场景整理成表格方便对照选择。模板类型区间定义while 条件收缩逻辑适合场景标准查找左闭右闭left rightleft mid 1 / right mid - 1无重复元素查找确切位置左闭右开左闭右开left rightleft mid 1 / right mid标准库风格通用性强边界变体左闭右开left right同左闭右开按条件收缩查找重复元素的左右边界如果只打算背一个模板应对大部分场景我推荐左闭右开版本。它能覆盖标准查找和边界查找且与 C STL、Python bisect 的区间语义一致理解后写变种时不需要反复调整边界。4. 实战从有序数组到二维矩阵与浮点数4.1 经典场景在旋转有序数组中查找目标值这是二分查找的高频面试题也是从“背模板”到“真会二分”的分水岭。题目是一个原本升序的数组在某个未知位置被旋转比如[4, 5, 6, 7, 0, 1, 2]在这个数组中查找目标值。核心思路是每次 mid 将数组分成两半至少有一半是严格有序的。先判断左半部分是否有序即nums[left] nums[mid]如果是检查 target 是否落在左半部分范围内是则收缩 right否则收缩 left如果左半部分无序则右半部分必然有序同理处理。def search_rotated(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 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 的区间判断必须使用半开区间写法nums[left] target nums[mid]不要拆成两个独立条件否则边界容易漏掉。4.2 经典场景二维矩阵的二分查找很多读者问二维矩阵怎么二分。其实思路是先定位行再在行内二分。有几种常见矩阵形态我分别说下处理方式。第一种是“每行内部有序、每行的第一个元素大于上一行的最后一个元素”的完全有序矩阵。这种可以直接把二维展成一维用一维二分处理。行号为mid // n列号为mid % nn 是列数。def search_matrix(matrix, target): if not matrix or not matrix[0]: return False m, n len(matrix), len(matrix[0]) left, right 0, m * n - 1 while left right: mid left (right - left) // 2 val matrix[mid // n][mid % n] if val target: return True elif val target: left mid 1 else: right mid - 1 return False第二种是“每行内部有序但列之间没有严格递增关系”的矩阵。这种情况就不能简单展平了需要用更巧妙的算法比如从左下角开始搜索。不过这不是二分查找的核心范畴这里不展开了。第三种是“每行每列都各自递增”的杨氏矩阵。这种矩阵的效率最高搜索方式也是从左下角或右上角开始每次排除一行或一列复杂度 O(m n)。严格说它不是二分查找但面试中常被归在“查找”大类里值得了解。4.3 浮点数二分精确度控制是核心二分查找不只是用于整数数组。在数值计算和机器学习领域浮点数二分也是常用工具典型场景是求解方程的根、单调函数的零点。浮点数二分的难点在于终止条件不是left right因为浮点数无法精确比较相等。需要用精度控制当区间长度小于某个阈值时停止或者迭代固定次数。def sqrt_binary(x, epsilon1e-7): if x 0: raise ValueError(negative input) if x 1: left, right x, 1 else: left, right 0, x while right - left epsilon: mid left (right - left) / 2 if mid * mid x: left mid else: right mid return (left right) / 2注意这里left mid或right mid都没有加减一因为浮点数不存在“下一个整数索引”只需要把边界收敛到目标精度即可。我习惯设定一个合理的 epsilon比如 1e-7同时最多迭代 100 次兜底防止极端输入下死循环。4.4 实战心得不要把二分只用在“数组”上我参与过一个配置系统需要根据时间戳快速定位某个版本生效期间的自定义配置。第一反应是写个遍历但配置数量上百万后每次查询遍历太慢。后来把配置按生效时间戳排序用二分查找“最后一个小于等于查询时间戳的位置”查一次从几十毫秒降到微秒级。这个场景的本质是任何满足单调性质的数据集合都可以用二分查找加速。时间戳排序天然满足单调性数值区间、日志偏移量、版本号列表都适用。所以学二分查找别只盯着数组题想要建立“单调有序就二分”的直觉。5. 死循环、溢出与边界场景问题排查实录5.1 经典死循环场景“mid 不前进”最典型的死循环发生在重复查找右边界时如果写成left mid而不是left mid 1当区间只剩两个元素时mid 恒等于 left导致 left 永远无法逼近 right。举例nums [1, 2, 2, 2, 3]target 2查找右边界。假设某轮left 1、right 2mid 1nums[mid] target满足条件如果执行left mid则 left 仍然是 1区间没有缩小下一次循环还是同样结果。解决方案在“需要保留 mid 作为候选”的情况下使用left mid 1或right mid来保证收缩如果实在需要left mid在循环体内加一个“若 mid left 则 break”的兜底逻辑但这样不优雅容易掩盖问题。5.2 整数溢出为什么要用减法求 mid(left right) // 2在 left 和 right 都很大时会溢出Java 和 C 的 int 溢出后变成负数直接导致 mid 指向错误位置。这是经典面试考点。正确写法是mid left (right - left) // 2。这个公式的数学含义是先算出区间长度的一半再加到 left 上结果与(left right) // 2相同但避免了加法溢出。在 Python 中整数不会溢出但养成这个习惯没有坏处因为你在面试时可能写的是 Java 或 C。我建议所有语言的二分查找实现都统一使用这个写法。5.3 边界场景空数组、单个元素、目标不存在、重复元素我整理了一份边界场景自查表每次写完二分查找代码按这张表过一遍基本能覆盖 90% 的问题。场景期望行为易错点空数组[]返回 -1 或指定位置初始化 left 0, right -1 时while 条件直接不满足返回 -1 是自然的单元素数组[x]如果 x target 返回 0否则 -1左闭右闭用 才能进入循环左闭右开用 也能进入目标在数组开头返回 0 或第一个匹配位置收缩逻辑必须允许 left 收缩到 0目标在数组末尾返回 len - 1 或最后一个匹配位置right 的收缩不能把最后一个元素排除掉目标不存在返回 -1或返回“应该插入的位置”插入位置场景需要理解 left 的最终含义全部重复元素返回左边界或右边界需要清楚自己写的是左边界还是右边界模板我实际刷题时发现许多人在“目标不存在”这一场景栽跟头。如果不清楚退出循环后 left 和 right 的含义就不知道应该返回插入位置还是 -1。这里有个通用结论在左闭右开模板下退出循环后 left 指向“第一个不小于 target 的位置”这个位置就是应该插入的位置。5.4 排查实战拿日志帮你看清循环过程如果代码异常但看不出原因我推荐一个调试技巧在循环体内打印 left、right、mid 三者的值跑几个小例子观察变化。以死循环为例打印后你会立刻看到left一直没有变化或mid一直等于left定位到问题就快多了。我写过不少次一开始也觉得打印日志太基础浪费时间但真到了复杂变种题里纸面推演和实际打印验证的差距很大。尤其是面试现场时间紧迫能快速用简单用例定位边界问题比硬推十行代码高效得多。6. 二分查找的进阶从“查找”到“答案”6.1 二分答案单调函数求极值二分查找的高级玩法是“二分答案”。核心思想是问题的答案是一个连续或离散的数值且这个数值具有单调性那么可以用二分搜答案空间代替直接求解。举一个经典例子给定一段木材的长度数组和一个目标段数 k问能切出的最大等长段长度是多少。暴力做法是从大到小枚举长度复杂度 O(n * max_len)。二分答案的做法是在长度空间[0, max_len]上二分每次判断当前长度能否切出 k 段判断是 O(n)总复杂度 O(n * log(max_len))。在机器学习相关的算法设计中这类思路也常见。比如找一个学习率区间的最优边界、找某个阈值使正负样本分割效果最优本质都是“在单调空间上求边界”二分答案的思想能直接迁移。6.2 二分查找与数据结构结合二分查找和数据结构结合的场景也很多。比如树状数组上二分查找前缀和位置用来解决“查找第 k 个大于某个值的元素”之类的问题再比如平衡树中的二分本质是在树上做类似的比较查找。这些进阶内容对面试和工程都有价值但绝不是基础学习阶段该碰的。先把一维数组的二分写到条件反射级别再去研究数据结构上的变体才比较稳妥。6.3 一个完整的二分答案实操案例我用一个业务场景来演示二分答案的实操过程。假设系统里有大量任务每个任务有独立的执行时长你希望把任务分配给 n 个 worker每个 worker 在单位时间内只能执行一个任务问完成所有任务的最短时间。这个问题用二分答案非常自然。def can_finish(tasks, workers, time_limit): # 判断在 time_limit 时间内 workers 个 worker 能否完成所有任务 count 0 for t in tasks: count (t time_limit - 1) // time_limit return count workers def min_time_to_finish(tasks, workers): left, right 1, max(tasks) while left right: mid left (right - left) // 2 if can_finish(tasks, workers, mid): right mid else: left mid 1 return left这个例子里can_finish就是单调函数时间越长越容易完成所有任务。二分搜最小时间每次判断时检查是否能完成左边能完成就收缩右边界不能完成就推进左边界最终 left 就是最短完成时间。这类问题在实际的需求排期、资源分配里经常遇到只是很多人没有意识到可以用二分答案来优雅处理。7. 语言差异与标准库使用杂谈7.1 Python 的 bisect 模块Python 标准库提供了 bisect 模块封装了二分查找的核心操作。它有bisect_left和bisect_right两个函数分别对应查找左边界和右边界。实际使用时bisect_left(a, x)返回第一个大于等于 x 的插入位置bisect_right(a, x)返回第一个大于 x 的插入位置。使用它的好处是效率高且不会有边界错误但代价是你必须理解返回值的含义。很多新手调用bisect_left后还要手动判断返回位置的值是否等于 target才能确定是否真的存在目标值。如果你已经熟练掌握了前面教的左闭右开模板那么 bisect 模块的返回值对你来说就是顺理成章的不需要额外记。7.2 C STL 的 lower_bound 与 upper_boundC 的algorithm库提供了lower_bound和upper_bound语义与 Python bisect 一致。前者返回第一个不小于 target 的迭代器后者返回第一个大于 target 的迭代器。两者相减就能得到数组中等于 target 的元素数量。STL 内部实现就是左闭右开区间的二分查找所以如果你能理解右开区间模板阅读 STL 源码时会非常顺畅。我在工作中写 C 时几乎不手写二分查找直接用 lower_bound但前提是理解它的行为否则遇到自定义比较器照样翻车。7.3 什么时候该手写二分虽然标准库很强大但有些场景必须手写需要在查找过程中同时记录额外信息比如比较次数、访问过的路径需要在非数组的数据结构上二分比如链表、文件偏移需要高度定制比较逻辑标准库接口不好表达面试或考核场景要求手写所以我建议标准库会用手写能力也要过关。两者不冲突反而相辅相成。理解手写本质后标准库用起来更自信熟练用标准库后写手写逻辑时也更清楚自己在干什么。8. 从零到一刷题路线与常见误区总结8.1 推荐的刷题顺序二分查找的题量不大但题型差异明显。我的建议是从最基础的查找开始按这个顺序刷第一梯队是标准二分查找在无重复有序数组中查找目标目标是不存在时返回 -1。这个题型一题就够关键是闭区间模板要滚瓜烂熟。第二梯队是查找左右边界数组中有重复元素要求分别返回第一个等于和最后一个等于 target 的位置。这个题型至少要刷三题因为实现细节不同容易混淆。第三梯队是二分答案比如切木头、爱吃香蕉的珂珂这类题目。重点在于怎么判断“答案是否可行”也就是写can_finish函数。第四梯队是变形题比如旋转有序数组、二维矩阵查找。这类题需要熟悉“部分有序”的判断方法。8.2 三个最高频误区第一个误区是把二分查找当成“只能查有序数组”。实际上只要数据具有单调性质无论是时间戳、得分、概率值都可以套二分模板。我见过有人面对“找到第一个满足某个复杂条件的位置”这类问题时毫无头绪其实题目只是换了一层业务皮核心还是二分。第二个误区是认为二分查找很简单所以不写测试用例。我自己踩过的坑写完模板自测一个正常数组通过了就以为没事。结果在单元素数组、空数组、目标在端点、重复元素这几个边界上全部翻车。后来我养成一个习惯每写一个二分相关函数先把这几个边界用例在脑子里过一遍或者直接在测试代码里跑一遍。第三个误区是过度优化。很多人喜欢在模板里写各种花式分支或者在循环里加特殊判断来提前退出。这些优化在面试中往往适得其反因为每加一个分支边界条件就多一层复杂度。二分查找本身 O(log n) 已经很快不要为了少一次循环把代码写到别人看不懂你自己三天后再看也看不懂。8.3 面试中的表达技巧面试时手写二分查找我建议按这个流程走先和面试官确认输入是否有序、是否有重复元素、返回要求是索引还是位置。这一步看似多余但能避免后续方向性错误。然后说明你的区间定义比如“我使用左闭右开区间”这能让面试官快速理解你的代码结构也显得你有逻辑。写完代码后自己举一个包含边界情况的例子走一遍比如[1, 2, 2, 4]target 分别是 0、2、5验证返回值是否符合预期。这个动作在面试中非常加分因为这显示了你会主动验证边界。最后如果面试官追问“还能怎么优化”可以提一下用位运算mid (left right) 1的写法但要说明这在语义上与除法等价并不是真正的优化重点。9. 写在最后的个人经验二分查找是算法里典型的“基础决定上层”的内容。我见过很多人花大量时间研究高级算法回头却在一道基础二分题上被卡住原因不是智商问题而是对边界条件的理解停留在“背模板”层面没有真正理解区间演变的逻辑。我个人在实际使用中的体会是把区间定义想清楚再动笔比写几十行代码重要得多。每次用之前花十秒钟问自己三个问题我用的是开区间还是闭区间while 条件是什么收缩时 mid 是否需要保留这三个问题想清楚了代码基本不会出错。最后再分享一个小技巧把二分查找模板记在脑子里之后不妨在平时的工作代码里刻意用一次。比如你需要在一个有序配置列表里查找某个阈值对应的配置项用二分替代遍历感受一下从十几毫秒到微秒级的速度变化。这种“学以致用”的成就感比刷一百道题都有用。这个内容后续还可以扩展到三分查找、二分图匹配、树上的二分等方向上但那是另一个话题了。先把基础的二分吃透后面的路自然会平坦很多。
