二分搜索避坑指南：从区间定义到边界条件全解析

提起 Binary Search 二分搜索我先说个自己踩过的坑。有一回在线上代码里排查一个“数组越界但偶现”的bug查到最后问题出在一处多线程状态查找的二分逻辑上——left 和 right 更新条件写反了某些数据分布下会死循环某些分布下又直接跳过正确区间。那次的教训让我意识到二分搜索虽然看着只有几行但边界、区间、终止条件这些细节真不是靠“背模板”就能稳住的。它在算法题里是最基础的入门级内容在真实工程里又是最容易被写歪的高频逻辑。所以这篇我想从“能直接用”的角度把二分搜索的原理、模板、变形、实战场景和排查心得一次说透。这篇内容适合谁看呢准备算法面试的、做后端和中间件开发经常写查找逻辑的、还有刚把数据结构捡起来想系统过一遍的都能从里面拿到可以直接抄作业的东西。我不会绕圈子讲一堆理论重点放在“怎么写对”“为什么这么写”“写错了会出什么事”上。1. 二分搜索到底在解决什么问题1.1 从一个最朴素的问题说起假设手里有一本按页码排好的电话簿你要找某个人的名字正常人不会从第一页翻到最后一页而是会先翻到中间看目标在左边还是右边然后丢掉另一半继续在剩下的部分里折半查找。二分搜索干的就是这件事在一个有序的数据结构里通过每次比较把搜索范围缩小一半把 O(n) 的线性扫描降成 O(log n) 的对数级查找。这里的“有序”是关键前提。LeetCode 上很多搜索类题目看着是乱序数组但旋转一下、部分排序一下本质还是在有序结构上做文章。所以二分的适用条件不是“数组是否有序”而是“能否通过一次中点比较排除掉一半不可能出现答案的区间”。1.2 为什么 O(log n) 这么重要2 的 10 次方是 10242 的 20 次方是 10485762 的 30 次方已经越过 10 亿。这意味着在 10 亿量级的数据里做查找线性最坏要找 10 亿次二分最多只要 30 次左右。数据库的 B 树索引、Redis 的跳跃表、有序数组的区间查询底层多多少少都能看到“折半”这个思想。我经常跟团队里新人说判断一个算法优不优秀先别看常数项先看它能不能在数据规模翻几百倍之后依然撑得住。二分搜索的 log n 特性决定了它是海量数据场景下的“骨架级”思想不是面试专用玩具。2. 写对二分搜索的三个关键2.1 区间定义是根一切边界都由它推出来我面试候选人时最喜欢问的第一句话是“你的 left 和 right 表示的是闭区间还是开区间” 很多人会愣一下因为背模板的时候从没想过这个问题。这里直接给结论写二分前第一件事是明确区间的数学定义。常见有两种闭区间写法[left, right]初始 left0rightn-1循环条件是 left right。左闭右开写法[left, right)初始 left0rightn循环条件是 left right。两种都能写对但你不能混着用。闭区间写法里left 和 right 都指向“可能包含答案”的位置所以当 nums[mid] target 时mid 已经被排除left 更新为 mid1当 nums[mid] target 时right 更新为 mid-1。左闭右开写法里right 指向“不包含答案”的边界所以更新时 right 直接取 mid 而不是 mid-1。建议新手就锁定其中一种长期使用我自己的习惯是左闭右开因为它在 lower_bound 这类“找第一个满足条件的元素”问题上更自然可以无缝对接 C 的 STL 习惯。2.2 mid 的计算竟然也有坑教科书里写的 mid (left right) / 2在真实工程里是可能溢出的。当 left 和 right 都是接近 int 上限的大数时两者相加会超过 2^31-1结果变成负数程序直接跑飞。正确写法是mid left (right - left) // 2上面的写法先算差值再加到 left 上从根本上避免了溢出。另一个等价方案是 mid left ((right - left) 1)位运算的右移一位等同于整除 2但只在非负整数上安全。Python 里用 // 就够了Java 和 C 里我习惯写成 left (right - left) / 2。还有一个细节是取中点时到底是偏左还是偏右。当区间内只剩两个元素时mid 会落在偏左的位置。这个特性在“找左侧边界”和“找右侧边界”时有微妙差异后面在变形题里详说。2.3 终止条件和死循环的渊源死循环是二分搜索最常见的运行时故障原因通常是“区间没有严格缩小”。拿闭区间写法举例很多人为了保险写了 while (left right)然后又在中点判断里写 left mid。这样一来当区间只剩两个相邻元素时mid 永远等于 leftleft 又被更新成 mid两个指针原地打转程序就死循环了。正确做法有两条路如果循环条件是 left right那每次更新必须执行 left mid 1 或 right mid - 1保证区间长度减少。如果循环条件是 left right那么 mid 的计算要配合更新方向。需要 left mid 时mid 必须向上取整即 mid left (right - left 1) / 2。这里没有“万能模板”只有“根据区间定义确保每次迭代都收缩”这一个原则。# 闭区间标准模板 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这份代码只要记住区间定义所有边界都能现场推出来nums[mid] 比 target 小说明目标只可能在右边left 越过 midnums[mid] 比 target 大说明目标只可能在左边right 越过 mid相等就直接返回。循环退出说明没有找到返回 -1。3. 从标准二分到 lower_bound 与 upper_bound3.1 为什么需要“找边界”而不是“找值”工程里大量场景不是“数组里有没有这个值”而是“第一个大于等于它的位置在哪”。比如查分数线成绩表按分数排序想知道多少人达到 60 分就要找第一个分数 60 的索引比如处理时间序列想知道某个时间点落在哪一条记录之后就要找第一个时间戳大于等于目标的位置。这就是 lower_bound 和 upper_bound 的用武之地。lower_bound 返回第一个不小于 target 的元素位置upper_bound 返回第一个大于 target 的元素位置。两者配合可以在一段连续区间内定位所有等于 target 的元素范围。3.2 一套模板通吃两种边界用左闭右开区间来写超级干净def lower_bound(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 return left核心区别在于当 nums[mid] target 时mid 本身可能是答案第一个target的位置所以不能丢掉它right 直接收缩到 mid当 nums[mid] target 时mid 肯定不是答案left 跳过它到 mid1。循环结束后left 和 right 重合指向的位置就是答案。upper_bound 更简单把判断条件改成 nums[mid] target 时 left mid 1其余时候 right mid返回的就是第一个大于 target 的位置。然后求“等于 target 的区间”就是start lower_bound(nums, target) end upper_bound(nums, target) # 如果 start end说明存在 target且区间为 [start, end)这套模板的好处是你不需要在循环里单独判断 nums[mid] target少一支分支逻辑更统一实测写错的概率小很多。3.3 循环结束后的兜底检查左闭右开模板的返回位置可能等于数组长度比如 target 比所有元素都大lower_bound 返回 len(nums)这是合法结果表示“找不到且应该插入到末尾”。使用的时候要习惯这种语义别一看到越界就觉得程序错了。反过来如果 target 比所有元素都小返回 0也合理。真正需要警惕的是在“找等于某值”的场景下拿到 lower_bound 的结果后不做任何检查直接访问数组可能访问到不存在的索引。正确习惯是拿到索引先判断是否在有效范围内再判断值是否真正等于 target。4. 实战旋转数组、二分答案与浮点二分4.1 旋转有序数组里怎么找最小值经典题一个原本升序的数组在某个未知位置旋转了一下比如 [4,5,6,7,0,1,2]要求找到最小值。这题不用比较 target而是比较 nums[mid] 和 nums[right] 的关系。思路是这样的如果 nums[mid] nums[right]说明最小值在右半边把 left 移到 mid1否则最小值在左半边或者就是 mid把 right 移到 mid。写成代码就是左闭右开式的旋转查找def find_min(nums): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] nums[right]: left mid 1 else: right mid return nums[left]这题两个易错点。一是比较对象选了 nums[left]在某些旋转场景下会失效二是 nums[mid] 和 nums[right] 相等的情况没处理好比如数组里有大量重复值此时二分退化需要配合线性收缩。面试时把重复值的情况聊清楚通常能加分。4.2 二分答案把“验证”当成判断函数二分搜索最容易被忽视的高级用法是“二分答案”。它不直接二分数据而是二分一个“答案的取值范围”再用某个验证函数判断当前值是否可行。举个例子经典的分割数组最大值问题把数组分成 m 段求各段和的最大值的最小可能值。范围从 0 到数组总和我们二分这个范围内的值然后贪心验证“每段和都不超过 mid 时能否在 m 段内装完”。如果能说明 mid 可以更小如果不能说明 mid 太紧需要放大。def can_split(nums, m, limit): count 1 cur 0 for x in nums: if cur x limit: count 1 cur x else: cur x return count m def split_array(nums, m): left, right max(nums), sum(nums) while left right: mid left (right - left) // 2 if can_split(nums, m, mid): right mid else: left mid 1 return left这种题的魅力在于真正难的不是二分本身而是设计出那个单调的验证函数。判断条件越清晰二分越无脑。工作中遇到的“最小化最大值”“最大化最小值”类问题都可以尝试往这个方向套。4.3 浮点数二分精度和循环次数怎么控float 或 double 数组上也能二分但终止条件不是 left right而是精度阈值比如 while (right - left 1e-7)。另外浮点数比较不建议直接用 因为浮点误差的存在几乎不可能精确相等。工程里我更推荐固定循环次数的写法比如循环 100 次。因为二分收敛是指数级的100 次迭代带来的精度已经远超 double 能表示的范围而且固定次数能保证不出现死循环也更容易预估耗时。浮点运算的开销比整数大但 100 次相对于 log 级别的收敛来说通常可以忽略不计。5. 工程里的二分搜索远不止“查找”5.1 实际业务里的几个典型场景很多人觉得二分只在算法题里出现其实生产环境到处都有它的影子。我参与过的项目里有做 IP 归属地查询的就是把几十万条 IP 段按起始地址排序然后二分定位目标 IP 落在哪一段有做风控规则引擎的把规则按优先级权重排序二分匹配命中的策略还有做内容推荐分桶的把用户画像分数排序后二分确定落在哪个实验组。这些场景都有一个共性数据量大、排序一次可以接受、查询极其频繁。线性扫描在百万级数据上可能只慢几十毫秒但放大到每天几十亿次调用差距就是可用性和不可用性的区别了。5.2 和数据结构结合的各种变体二分思想最常见的“变形”藏在各种高级数据结构里。有序数组的直接二分是最朴素的形态。二叉搜索树的查找本质上就是在一棵“天然支持二分”的树结构上做比较。B 树索引的叶子节点是排好序的链表数据库会在节点内部做二分定位。跳跃表的每一层都相当于一个稀疏索引上的二分查找。所以“二分搜索”不是一个孤立的算法而是一整套“利用有序性加速查找”的世界观。理解了这一层再看很多中间件源码会突然明白那些索引结构为什么长这样。6. 常见问题与排查技巧实录6.1 问题速查表我把这几年在算法题里、代码评审里、线上故障里遇到的二分问题整理成了一张速查表方便你写完代码后对着检查。症状可能原因修复思路死循环mid 更新没有收缩区间闭区间写法用 mid1/mid-1左闭右开配合 leftmid 时 mid 取上取整返回结果差一位区间定义混乱right 写成 n-1 还是 n 没想清统一用左闭右开right 初始化为数组长度找不到已存在的元素循环条件用了 left right 且未处理相等情况确认循环条件和更新条件配对或者改用 lower_bound 模板数组中有重复值时结果不对没有区分“第一个”还是“任意一个”等于 target需要精确边界时用 lower_bound / upper_boundmid 运算溢出直接 left right 相加改成 left (right - left) // 2浮点二分无限循环循环条件写成了 left right改用精度阈值或固定循环次数6.2 我总结的几个独家避坑习惯第一写完二分先手工验证三个场景数组只有一个元素、目标在数组首尾、目标不存在。这三个场景覆盖了绝大多数边界错误。第二尽量用左闭右开的模板。它有一些反直觉的地方比如 right 初始是数组长度而不是 len(nums)-1但正因为如此循环结束时 left 直接就是“插入位置”语义非常干净。一旦你从闭区间切到半开区间很多边界问题会自然消失。第三在代码评审里看到二分先问“区间不变量是什么”。如果对方答不上来代码大概率有问题。这不是刁难因为凡是能清晰说出不变量的二分出错的概率极低。第四线上问题优先怀疑 mid 的更新和边界收缩是不是匹配。死循环和越界90% 都出在这两个位置别急着怀疑数据问题。以我个人的体会二分搜索是那种“看别人写觉得简单自己写总是差一点”的算法。关键不在于记几个模板而是把区间定义和更新规则内化成一种思维习惯。你在刷题或写代码时只要每次写二分前先默念三句话区间是什么、退出条件是什么、每次循环区间是否在缩小就能避开绝大多数经典陷阱。最后再分享一个小技巧如果你要处理的问题能写成“关于某个参数单调递增或递减的判断函数”那么它大概率可以用二分来解。这个认知比会背十个二分模板都值钱。后续自己在项目里遇到排序数据上的查找、范围统计、最优解搜索不妨先想想二分很多时候它能帮你把问题从 O(n) 级别直接压到 O(log n) 级别。