二分查找算法详解：从边界条件到模板与实战应用

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 模板选型建议

我把三个模板的适用场景整理成表格，方便对照选择。

如果只打算背一个模板应对大部分场景，我推荐左闭右开版本。它能覆盖标准查找和边界查找，且与 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 % n，n 是列数。

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, epsilon=1e-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 = 2，mid = 1，nums[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% 的问题。

我实际刷题时发现，许多人在“目标不存在”这一场景栽跟头。如果不清楚退出循环后 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_bound

C++ 的<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 是否需要保留？这三个问题想清楚了，代码基本不会出错。

最后再分享一个小技巧：把二分查找模板记在脑子里之后，不妨在平时的工作代码里刻意用一次。比如你需要在一个有序配置列表里查找某个阈值对应的配置项，用二分替代遍历，感受一下从十几毫秒到微秒级的速度变化。这种“学以致用”的成就感，比刷一百道题都有用。

这个内容后续还可以扩展到三分查找、二分图匹配、树上的二分等方向上，但那是另一个话题了。先把基础的二分吃透，后面的路自然会平坦很多。