二分查找这个算法我在面试别人的时候几乎每次都会问自己也反反复复手写过无数遍。它看起来太简单了——一个有序数组找一个目标值折半、判断、再折半循环几次就能出结果。但真正能在白板上一次写对、把边界条件讲清楚的人其实不多。这个算法最迷人的地方在于它用 O(log n) 的时间解决了一个最朴素的查找问题在四十亿条有序数据里定位一个目标值最多只需要比较三十二次。这背后是计算机科学里非常重要的一种思维——每次迭代都砍掉一半的搜索空间。这篇内容想把二分查找这件事彻底讲透。不管你是刚开始学数据结构与算法的新手还是在准备算法工程师面试、刷 LeetCode 的进阶玩家甚至只是工作中要处理有序数据的检索、要理解数据库索引原理的工程师这篇都应该能给你一些可以立刻用上的东西。我会从最基础的原理讲起带到标准代码的边界陷阱、四个经典变体、二分思想的扩展场景再回到工程实践和面试考察点上尽量把每一步背后的“为什么”也说清楚。1. 二分查找的本质为什么“折半”能跑赢“逐个找”1.1 从猜数字游戏说起小时候都玩过这样的游戏对方心里想一个 1 到 100 之间的数字你每次猜一个数对方告诉你“大了”还是“小了”直到猜中为止。如果老老实实从 1 猜到 100运气好的话一次命中运气不好要猜一百次。但如果每次都猜中间值——先猜 50然后根据提示决定去 1~49 还是 51~100 继续折半——你会发现最多只需要猜七次。这就是二分查找最直观的感受每次都能排除一半的错误答案而不是排除一个。这个策略的本质是目标值所在的范围是确定的每次比较都会把当前范围分成两半其中一半可以彻底丢弃因为有序性保证了目标值不可能出现在被丢弃的那一半里。这种“基于信息量做排除”的思路和顺序遍历有本质区别。顺序遍历每次只排除一个元素信息利用率极低二分查找每次排除一半信息利用率是指数级的。1.2 时间复杂度到底怎么算假设数组长度为 n第一次查找后范围变成 n/2第二次变成 n/2²不断折半直到范围缩小到只剩一个元素。这个过程需要经过 k 次折半满足 n / 2^k 1解得 k log₂n。所以二分查找的时间复杂度是O(log n)空间复杂度是O(1)因为我们只需要维护左右两个指针。O(log n) 意味着什么n 1,000,000 时log₂n 大约是 20n 10,000,000,000 时log₂n 大约是 34。也就是说即使数据量从一百万涨到一百亿二分查找需要执行的比较次数只从 20 涨到 34。这种增长速度在算法领域属于极快的类别。作为对比顺序查找的时间是 O(n)数据量翻十倍耗时也翻十倍二分查找数据量翻十倍耗时只是增加几次常数操作。1.3 三个前提条件缺一个都不成立二分查找不是万能的它有严格的适用前提这一点在实际工程里特别容易被忽略。第一个前提是数据必须有序。如果数组是无序的折半就没有依据——你无法判断目标值应该去左半边还是右半边找。当然不排序也有补救办法比如先排序再查找那是一套“排序 二分”的组合拳代价是排序本身要 O(n log n)。如果只查一次排序可能不划算如果查很多次排序一次、二分多次收益就非常明显。这也是搜索引擎后台、数据库系统里常见的策略。第二个前提是支持随机访问。二分查找需要直接跳到数组中间位置这要求数据结构能在 O(1) 时间内按下标访问元素。数组和 vector 都满足链表就不满足——链表定位中间节点需要从头遍历每次折半的成本都是 O(n)整体复杂度退化成 O(n log n)还不如一次顺序遍历来得快。这也是为什么在链表上用二分查找很少见的原因。第三个前提是存在单调性。二分不只适用于数组值的大小顺序更通用的条件是问题的答案空间呈现单调特性——“满足某个条件”和“不满足条件”之间存在清晰的分界线。理解了这一点才能理解后面要讲的“二分答案”思想为什么能在无穷多场景里发挥作用。2. 标准二分查找的三种写法与边界陷阱2.1 最经典的闭区间写法先给出最常见的闭区间版本C 风格的逻辑可以无缝迁移到其他语言int binarySearch(vectorint nums, int target) { int left 0; int right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return -1; }这段代码里区间用[left, right]表示左右边界都是闭区间也就是左右两个位置本身也在搜索范围内。所以循环条件必须用left right因为当left right时区间里还有一个元素没检查。每次比较后如果目标值在右侧left mid 1因为mid已经检查过了不需要再保留在区间里如果目标值在左侧同理right mid - 1。闭区间写法是大多数人最早接触的版本也是面试中最容易讲清楚的版本。它的循环不变量是目标值如果存在一定位于闭区间 [left, right] 中。每次迭代都在不破坏这个不变量的前提下缩小范围这是二分查找正确性的核心依据。2.2 左闭右开写法另一个常见版本是左闭右开区间[left, right)在 STL 和很多基础库里使用频率很高int binarySearch(vectorint nums, int target) { int left 0; int right nums.size(); while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid 1; } else { right mid; } } return -1; }注意这里right初始值是nums.size()而不是nums.size() - 1因为right表示的是“开区间”的右边界——它指向的范围不包含自身。循环条件也从left right变成left right因为当left right时区间为空已经没有任何元素需要搜索了。当目标值在左侧时right mid而不是mid - 1因为已知mid不是目标值但mid本身又不在[left, right)的范围内可以让right直接收敛到mid。这个写法的好处是空区间直接返回哨兵位置可以指向end()在 C 的迭代器世界里非常自然。2.3 三个版本之间的换算关系把三种写法记住最好的方式是把它们当作同一个逻辑的三套“坐标系统”闭区间[l, r]循环l r左移r mid - 1右移l mid 1左闭右开[l, r)循环l r左移r mid右移l mid 1开区间(l, r)循环l 1 r左移r mid右移l mid很多人在面试中写错往往是因为三种写法混着用——一会儿用闭区间的循环条件一会儿用左闭右开的边界更新。写之前先想清楚“当前区间到底包不包含右边界”这个问题解决了代码基本不会错。2.4 一个必须避开的坑整数溢出mid的计算在经典教材里是(left right) / 2这在数值较小的时候没问题。但left right可能超过 int 类型上限。在 Java 或 C 中int 最大值是 2147483647如果left和right都是接近上限的数相加会出现整型溢出得到负数程序直接出错。正确写法是int mid left (right - left) / 2;这个公式的本质是把“从 left 开始再走一半的距离”作为中间下标right - left最多不会超过数组长度基本杜绝了溢出问题。这是我写二分时几乎形成肌肉记忆的一行代码也建议你在实现时直接当成标准写法。3. 二分查找的四个经典变体从“找一个数”到“找一段区间”基础版二分查找解决的是“找一个准确相等的目标值”。但真实世界里更常见的问题是目标值可能不存在或者存在多个我需要的是第一个大于等于它的位置、最后一个小于等于它的位置。这些都可以通过二分查找在 O(log n) 时间内解决关键是要理解变体的边界逻辑。3.1 查找左边界第一个不小于 target 的位置这个操作在很多语言里就叫lower_boundPython 的bisect_left也是同一个思路。它的返回值是数组中最左边那个大于等于 target 的元素下标。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 小可以全部排除所以left mid 1否则mid可能是第一个不小于 target 的位置也可能在它左边还有更合适的位置所以保留mid本身right mid。循环结束时left right这个下标就是答案。如果所有元素都小于 target返回len(nums)。3.2 查找右边界最后一个不大于 target 的位置对称地upper_bound在 C 里返回的是第一个大于 target 的位置而“最后一个不大于 target 的位置”就是upper_bound - 1。直接用二分实现def upper_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 # 返回的是第一个大于 target 的位置注意这里的条件换成了nums[mid] target等于 target 时也把左边界右移目的是跳过所有相等的元素。最终返回的位置是所有等于 target 的元素的下一个位置。想找最后一个等于 target 的位置用upper_bound(nums, target) - 1即可。3.3 左边界和右边界在排序数组中的应用有了这两个操作很多原本需要手写一堆逻辑的问题可以变成组合调用查找目标值是否存在于有序数组lower_bound找到下标检查下标不越界且值等于 target统计 target 出现的次数upper_bound - lower_bound两个 O(log n) 操作配合得行云流水寻找插入位置在有序数组中插入一个值并保持有序下标就是lower_bound在 C STL 里这些功能早就封装好了直接用std::lower_bound和std::upper_bound就行Python 里用bisect模块Java 里用Arrays.binarySearch的返回值做微妙处理。但面试的时候大概率会让你从零实现一遍所以自己动手写出无 bug 版本是基本功。3.4 左边界写法的统一模板我给一个不容易记乱的统一模板后续所有变体都可以基于它推导def binary_search_left(nums, target): left, right 0, len(nums) while left right: mid left (right - left) // 2 if 条件成立: right mid else: left mid 1 return left对于 lower_bound条件成立就是nums[mid] target对于 upper_bound条件成立是nums[mid] target。如果你写的是“返回最后一个满足某条件的值”只需要在 left 移动时记录候选答案或者最后返回left - 1。这个模板把“找边界”问题统一成了“找第一个满足条件的位置”条件由题意决定区间的更新规则完全固定特别适合用来推演不熟悉的二分变体题。4. 二分思想“出圈”从有序数组中扩展到更多场景二分查找真正的强大不只是在一个有序数组里找数字。它的思想可以泛化到任何“答案具有单调性”的问题上这就是所谓的“二分答案”。热词里也有不少二分相关的搜索词比如“二分查找pta函数”“算法流程图”说明大家平时学的就是这些基础应用但基础之上还有非常广阔的空间。4.1 二分答案把最优化问题变成判定问题有一类问题正着做很复杂求一个最优值比如“数组分成 m 段之后每段和的最大值最小是多少”。这类问题最好的入手方式不是直接找最优解而是先写一个判定函数check(x)回答“最大段和不超过 x 时能不能把数组分成 m 段”。这个 check 函数在满足条件一边是 true、另一边是 false 时答案空间天然具备单调性——x越大越容易满足。所以可以在 x 的取值范围上做二分查找最终收敛到满足条件的最小值。这种“对答案本身二分不断调用判定函数”的模式在编程竞赛和算法面试里出现频率极高。它和普通二分数组的区别是二分对象从具体的数组元素变成了抽象的数值范围判断依据从“值的大小比较”变成了“条件是否满足”。剩下的框架和标准二分完全一样。4.2 求平方根连续函数上的二分一个经典例子是求非负整数 x 的整数平方根。LeetCode 上对应的题目是“x 的平方根”。思路是在[0, x]范围内二分查找最大的 mid 满足mid * mid x。这本质上是右边界查询——找最后一个满足条件的位置。def my_sqrt(x): left, right 0, x 1 while left right: mid left (right - left) // 2 if mid * mid x: left mid 1 else: right mid return left - 1如果 x 很大mid * mid可能溢出要用mid x // mid来替代。这个例子很好地展示了二分的边界条件是如何被“条件成立”的具体含义驱动的。4.3 浮点数二分精度控制是关键二分还可以用在连续实数域上。假设要求一个函数 f(x) 的零点f 单调递增且已知 f(0) 0、f(10) 0。这时可以不断折半区间直到区间长度小于某个精度阈值比如 1e-7然后返回区间中点。浮点数二分和整数二分最大的区别在于循环条件不再依赖left right而是改为right - left eps。eps的选择要结合问题精度要求如果题目要求保留 6 位小数eps取 1e-8 比较稳妥防止舍入误差导致结果差一点。浮点数溢出的问题不再显著但死循环风险依然存在——如果eps设得太小远小于浮点数的机器精度循环可能迟迟不结束。4.4 旋转排序数组的二分这也是算法面试高频题一个原本有序的数组在某个位置发生了旋转比如[4,5,6,7,0,1,2]在其中查找目标值要求 O(log n)。这个问题的核心思路是mid 把数组分成一半其中一半一定仍然有序。利用有序半边判断目标值是否在其中然后决定去哪个方向继续二分。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这个题考察的不只是二分模板而是你能不能判断出“哪半边有序”并且据此缩小搜索范围。理解了这层“逼近”思想旋转数组、寻找旋转点、找到顶峰值这一类题都可以迎刃而解。5. 工程实践二分查找在生产环境中的真实身影5.1 数据库索引内部的二分查找数据库里的 B 树索引内部每个节点存了一组有序的键值查找某个 key 时在节点内部用的就是二分查找来定位应当进入哪个子树或者命中哪个记录。一个层级内部只有几十到几百个键二分是性价比极高的选择——每次查一个节点只要 O(log m) 次比较m 是节点内的键数。Redis 的跳表实现里查找路径也借鉴了类似的思想从高层往低层逐层逼近目标每一层都尽量跳过足够多的元素。虽然跳表不是数组但它用“有序 多层索引”复现了二分查找的跳跃感。理解二分的思想能帮助你理解更多底层组件的设计。5.2 标准库里被封装好的二分绝大多数标准库都已经内置了二分查找日常业务开发直接调用即可Pythonbisect模块bisect_left和bisect_right是主力注意排序列表才能用Cstd::binary_search只返回布尔值std::lower_bound和std::upper_bound返回迭代器JavaArrays.binarySearch查找成功返回下标失败时返回-(insertion point) - 1的负数用于推导插入位置自己实现二分的能力更多体现在面试和特殊场景上生产代码中不如直接调用久经考验的标准库实现减少边界 bug 的概率。但前提是你要理解它们的行为——比如 Java 返回值怎么转成插入位置bisect_left和bisect_right在重复元素时的区别这些都是实际工程里会踩到的地方。5.3 二分查找与排序、哈希的取舍热词里出现了“排序算法”“数据结构与算法”而且二分和排序经常成对出现。一个常见的工程套路是数据频繁查询且对内存不敏感时先一次性排序然后每个查询走二分如果数据量小顺序遍历往往更简单直接因为 CPU 缓存命中率高常数项小O(n) 未必输给 O(log n)。如果查询量极大且对精确匹配要求高哈希表可能是更好的选择——用空间换时间O(1) 的平均查询时间比二分更快但代价是无法做范围查询、无法保持有序性。二分查找的独特位置在于它同时支持精确查找和范围查找不占用额外内存且元素越多优势越明显。如果你需要在有序数据上频繁做“找大于等于某个值的第一个元素”“统计区间内元素个数”二分几乎没有替代方案。5.4 大规模数据与外部查找当数据量大到内存放不下时二分就演变成了外部存储的查找策略。B 树之所以成为数据库索引的默认结构正是因为它在磁盘上也保持了“每层近似二分”的特性能够用很少的磁盘 I/O 定位到目标数据。理解这一点后你会发现二分查找从内存数组到数据库再到分布式系统的扩展是同一个思想在不同介质上的延续。6. 算法面试考察点与常见 Bug 排查6.1 面试官到底在考什么算法工程师面试里二分查找几乎是必考题。但它太简单了简单到很多候选人掉以轻心。面试官通过这道题通常会考察三个维度第一边界条件是否考虑全面空数组、一个元素、两个元素、重复元素是不是都能正确运行第二代码风格是否稳定mid的计算方式、循环不变量的声明是否清晰第三能不能现场推导变体比如让你写 lower_bound 然后改成 upper_bound或者问“找峰值元素能不能用二分”。我当面试官时见过不少候选人能背出模板但是一旦我改变条件比如改成“数组里有重复元素找最左边的目标值”就会卡壳。这说明他没理解二分搜索树上的“判断条件”是怎么随着题意变化的。我的建议是不要只背模板要把左边界、右边界、闭区间、开区间之间的换算关系练到条件反射。6.2 高频 Bug 清单第一个高频 bug 是死循环。典型场景写左闭右开区间时循环条件是left right但在else分支用了right mid - 1一旦目标值在左半边区间更新后可能把 mid 排除掉了但循环还能继续更危险的是left mid配合left right在 left 和 right 相邻时会造成死循环——因为 mid 一直等于 leftleft 无法前进。解决这个问题的方法是始终牢记区间不变量要求每次循环结束时区间严格缩小left mid只有在循环条件为left 1 right时才安全。第二个高频 bug 是边界外访问。初始化right nums.size()后直接访问nums[right]会越界尤其是在某些条件分支里。注意左闭右开区间里right是「哨兵」不应该被读取。第三个高频 bug 是重复元素处理不统一。找左边界和找右边界判断条件里的等号很容易写反——nums[mid] target还是nums[mid] target决定了是跳过小于等于还是只跳过小于的元素。建议用 3.3 节给的模板来推导不要在考场上临时想。6.3 配套练习与刷题路径想巩固二分查找我推荐的练习路径是基础在有序数组中查找目标值练习闭区间和左闭右开两种写法边界实现lower_bound和upper_bound处理重复元素应用搜索旋转排序数组、寻找峰值、求平方根、猜数字大小进阶二分答案题比如“分割数组的最大值最小化”“爱吃香蕉的珂珂”“在 D 天内送达包裹的能力”综合二叉搜索树与二分思想结合理解树形结构和数组二分的同构性这个路径下来二分相关的面试题基本都能覆盖。6.4 调试二分的一个独门技巧写二分容易出 bug 的时候我建议把这个“全等于”问题当成一个纯函数来调试首先固定使用左闭右开区间模板把条件提取成单独的函数condition(mid)让主循环只负责移动指针不要在里面堆业务逻辑。这样调试时就能把一个复杂问题简化成“循环边界 判定函数”问题立刻清楚很多。我调试的时候还会故意测试这几个用例空数组、单元素数组、target 比所有元素都小、target 比所有元素都大、target 恰好是第一个元素、恰好是最后一个元素、有大量重复元素。这七个用例跑一遍99% 的边界 bug 都能暴露出来。这个习惯建议保留到正式开发中——凡是用到自定义二分的地方先写这两个用例再上线。7. 再补充一点二分和二叉树的思想呼应如果你学完了二分查找不妨把目光放高一点去看数据结构与算法里其他相关内容。二叉搜索树本质上就是“二分查找的树形版本”。数组二分每次取中间节点二叉搜索树则是把一个集合组织成一棵树每个节点左子树的值都小于节点值右子树的值都大于节点值查找过程就是在树上每层决定向左还是向右。两者都是 O(log n) 的查找复杂度区别只是数据组织方式不同。热词里出现了“分治算法”和“归并排序算法”归并排序就和二分有着天然的联系——分治的第一步就是“把数组从中间切开”递归处理左右两半再合并结果。很多算法都是从二分这种“一刀切两半”的思维方式延伸出去的。理解了二分的思维方式后续学归并排序、快速排序、二叉平衡树、线段树都会顺畅很多。我个人在实际写代码时还有一个很深的体会二分查找看似简单但它是那种“会者不难难者不会”的算法。它考察的是你对区间不变量的理解、对问题单调性的敏感度以及动手前想清楚边界的习惯。建议把本文的模板抄下来自己手写三遍——第一遍看着写第二遍合上代码自己写第三遍换一种区间写法试试。写完这三个版本之后遇到任何二分变体题你都会觉得“换汤不换药”。最后分享一个小技巧做题时如果实在不确定边界条件可以在纸上把一个长度为 5 的数组完整跑一遍这个流程手动模拟每一步的 left、right、mid 变化。我面试和带新人的时候发现不少人靠这一步就能自己找到 bug 所在。二分查找要真正成为肌肉记忆靠的就是这种反复的“手动追踪”。