相信大家对猜数字游戏都不陌生一个人在 1 到 100 之间想一个数你每次猜完对方只会告诉你大了还是小了用最快的方式猜中它——没有人会从 1 开始挨个试因为二分查找这个思想在生活里早已根深蒂固。但就是这么一个人人都懂思想的算法放到代码里却让无数人在面试现场翻车甚至工作三五年的老手在不查资料的情况下也未必能一次写对。我今天想好好聊聊二分查找算法从它为什么快、怎么写才不出错、到各种变体和真实项目中的运用一次讲透。这篇文章适合所有刚接触数据结构的初学者、正在准备算法面试的求职者以及那些会用但说不清的开发者。我会用大量实际代码和踩坑记录来讲尽量让你看完能直接上手而不是停留在好像懂了的层面。1. 从 O(n) 到 O(log n)二分查找到底凭什么快1.1 猜数字游戏里的数学直觉回到最开头的猜数字游戏。1 到 100 之间猜一个数如果用二分策略第一次猜 50第二次根据反馈猜 25 或 75每次都把剩余范围砍掉一半。最多猜几次能保证猜中答案是 7 次左右因为 2 的 7 次方是 128刚好覆盖 100 个数。这就是二分查找的核心逻辑每比较一次搜索范围就缩小一半。这个过程用数学语言描述就是在一个长度为 n 的有序序列中查找某个目标值最多需要 log₂(n) 次比较。这听起来好像没什么但当你把 n 放大差距就变得非常恐怖。我列一组数据对比数据规模 n线性查找最坏次数二分查找最坏次数100100710,00010,000141,000,0001,000,000201,000,000,00010 亿30看到没有当数据量到 10 亿级别时线性查找要比较十亿次而二分查找仅仅需要 30 次。这就是为什么说二分查找不是稍微快一点而是从量级上碾压了顺序查找。1.2 复杂度背后的前提代价当然二分查找不是没有代价的它有两个硬前提数据必须有序且必须支持随机访问也就是能通过下标直接取到中间元素。很多人会忽略第一个前提背后的深层含义如果你有一组无序数据先用排序再二分查找总的成本是排序的 O(n log n) 加上查找的 O(log n)。那什么时候这样做是划算的答案是当同一份数据你要查很多次的时候。排序是一次性投入之后每次查找都能享受对数级别的效率。反过来如果数据本身就是动态增长的每次插入都要保持有序那么插入成本会从 O(1) 变成 O(n)——这一点在工程里常常被忽略后面我会专门讲。第二个前提限制的是数据结构。链表理论上也可以二分但你无法 O(1) 跳到中间节点每次取 mid 都要从头遍历时间复杂度退化到 O(n log n)还不如直接线性扫描。这也是为什么数组和基于数组的结构如 ArrayList、vector最适合二分查找而链表类结构LinkedList很少用二分的原因。1.3 效率的代价不止在时间额外说一点二分查找还有一个隐性优势在很多资料里不会提它对 CPU 缓存非常友好。因为每次比较都集中在数组的某个局部区域不像跳表或哈希表那样需要频繁随机访问内存。在现代计算机的分层存储架构下这种局部性带来的实际加速往往比理论复杂度对比更明显。实测中对百万级有序数组做大量查找二分查找比哈希查找在某些场景下还快就是因为缓存命中率高。这一点在性能敏感的系统里值得好好利用。2. 标准实现拆解这份代码模板我建议你直接背下来2.1 最经典的 C 写法先给出最经典、最不容易错的模板我用 C 写因为网络热词里c 二分查找出现频率很高而且 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 mid 1写成left mid最后陷入死循环。下面我把每个关键点拆开讲。2.2 逐行拆分为什么每个符号都不能乱改区间定义左闭右闭[left, right]这个模板用的是左闭右闭区间也就是left和right指向的元素都在当前搜索范围内。初始化right nums.size() - 1意味着数组最后一个元素也在搜索范围内。很多教科书会写成right nums.size()那就是左闭右开区间[left, right)搜索范围不包括right指向的元素。两种都行但必须从头到尾保持一致。我最推荐初学者先死死记住左闭右闭这一种因为它的循环条件和后续的边界收缩最直观。循环条件while (left right)因为左闭右闭区间里left right时区间里还有一个元素需要检查所以循环条件必须是。如果写成当left right时循环退出这个元素就被漏掉了。中间位置int mid left (right - left) / 2很多人会写成int mid (left right) / 2这在大部分情况下没错但当left right超过 int 最大值时会溢出。虽然日常开发很少遇到这种极端数据但严谨的算法代码应该避免这个隐患写成left (right - left) / 2就永远不会溢出。区间收缩left mid 1和right mid - 1当nums[mid] target时说明目标值在右半部分mid 位置已经检查过了所以左边界要缩到mid 1。反过来就是right mid - 1。这里的1和-1是最容易出错的地方如果写成left mid或right mid在只剩两个元素时就会死循环。我们验证一下假设区间[2, 3]left 2, right 3mid 2。如果nums[mid] target且执行left mid那么新的区间还是[2, 3]无限循环。只有left mid 1才能让区间变成[3, 3]继续检查最后一个元素后退出。2.3 两种区间风格左闭右闭和左闭右开既然提到左闭右开我也给出对应的模板方便大家看懂网上不同版本的代码int binarySearch(vectorint nums, int target) { int left 0; int right nums.size(); // 注意这里不是 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; // 注意这里不是 mid - 1 } } return -1; }左闭右开区间[left, right)中right指向的元素不在范围内因此循环条件是left right相等就说明区间为空右边界收缩时right mid即可因为 mid 不在新范围内。这套写法的好处是right - left正好等于区间长度配合 STL 的迭代器语义比较自然。我的建议是选一种你真正理解且用得顺手的用到烂熟。不要在两种之间反复横跳否则最容易出错。3. 那些让老手都翻车的边界细节死循环、溢出与区间开闭3.1 死循环从哪来取整方向与区间收缩的匹配我前面提到left mid会造成死循环但为什么有些博客的代码确实这么写也没事因为他们处理的是查找左边界这类变体使用的取整方向不同。这里有一个核心规律当区间收缩是left mid时mid 的计算必须向上取整当收缩是right mid时mid 必须向下取整。向上取整的写法是int mid left (right - left 1) / 2。你可能会问为什么原因在于当区间只剩两个元素时比如[2, 3]向下取整得到mid 2。如果此时执行left mid新区间还是[2, 3]死循环。但如果向上取整得到mid 3执行left mid后区间变成[3, 3]成功收缩。凡是写过二分查找变体的人几乎都在这个坑里栽过。我的经验是写完后一定用两个元素的区间在草稿纸上推一遍不要嫌麻烦这比事后调试省时间得多。3.2 整数溢出mid 计算的隐蔽风险前面说了(left right) / 2在极端情况下会溢出这里再展开讲一下。Java 和 C 中 int 最大值是 2,147,483,647如果数组长度接近这个数left right就会溢出成负数导致 mid 计算错误程序直接崩或者进入奇怪的逻辑分支。在 Python 里不存在这个问题因为它的整数是任意精度的但在 C、Java、Go 里都必须注意。left (right - left) / 2这个写法不仅是避免溢出而且在任何情况下都不会出错所以我也建议所有语言都统一用这种写法。它带来的性能差异可以忽略不计但能干掉一整类 bug。3.3 我调试边界问题的一个笨办法分享一个自己常用的调试手段在循环里打印left、right、mid三个变量。while (left right) { int mid left (right - left) / 2; printf(left%d, right%d, mid%d\n, left, right, mid); // ... }当你怀疑边界有问题时把这三个值打出来跑一遍就一目了然。比如死循环时你会看到 left 和 right 一直不变立刻就能定位到是那次区间收缩写错了。这个办法虽然笨但比盯着代码猜有效得多。还有一个更系统的方法写一个包含 0、1、2、3、4 个元素的测试用例覆盖目标值在最左边、最右边、中间、不存在、比所有元素都小、比所有元素都大这六种情况。把这些跑通了你的二分实现基本就稳了。4. 二分查找的四类高频变体找位置、找边界、旋转数组与二分答案4.1 找左边界和右边界lower_bound / upper_bound标准二分查找是找一个确定的值但工作中更常见的是找第一个等于 target 的位置或找最后一个小于等于 target 的位置。这两个操作在 C STL 里有现成的函数lower_bound和upper_bound但面试或某些场景下需要你手写。手写找左边界的模板int lowerBound(vectorint nums, int target) { int left 0; int right nums.size(); // 左闭右开 while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { right mid; // mid 可能是答案不能排除 } else { left mid 1; } } return left; }这个模板的关键在于nums[mid] target时不能直接返回因为左边可能还有等于 target 的元素所以要收缩右边界到 mid把等于的情况也包含在范围内继续向左找。最终返回的left就是第一个大于等于 target 的位置。找右边界第一个大于 target 的位置只需把条件改成nums[mid] target。这两个函数配合使用就能在有序数组里统计某个值的出现次数upperBound(target) - lowerBound(target)。这个技巧在工程里非常常用比如统计某个分数段的人数、某个价格区间内的商品数量。4.2 旋转有序数组里查找目标值旋转有序数组是面试中另一道高频变体题一个有序数组在某个位置被旋转了比如[0,1,2,4,5,6,7]变成[4,5,6,7,0,1,2]让你在其中查找目标值。这种题的核心洞察是每次取 mid 后左半部分和右半部分至少有一半是有序的。利用这个性质判断 target 落在哪个有序半区即可继续二分。int search(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) return mid; if (nums[left] nums[mid]) { // 左半部分有序 if (nums[left] target target nums[mid]) { right mid - 1; } else { left mid 1; } } else { // 右半部分有序 if (nums[mid] target target nums[right]) { left mid 1; } else { right mid - 1; } } } return -1; }这个实现的难点在于判断哪一半有序并确认 target 是否在有序的那一半里。我第一次写这个题时犯了两个错误一是没注意到nums[left] nums[mid]必须用而不是因为当 left 和 mid 指向同一个元素时左半部分只有一个元素也算有序二是 target 的边界条件写成了开区间导致漏掉端点值。这个题建议多写几遍最好把几种旋转情况都推演一遍。4.3 二分答案让二分从查找进化为求解二分查找最强大的变体其实是二分答案也叫单调函数求值。它不直接在数组里找元素而是对一个满足单调性的函数进行二分搜索逼近问题的解。一个经典例子是求解平方根给定一个非负整数 n求其平方根的整数部分要求不使用库函数。这个问题等价于找到一个最大的整数 x使得x * x n。因为x^2关于 x 是单调递增的所以可以对 x 做二分。int mySqrt(int n) { int left 0, right n; while (left right) { int mid left (right - left) / 2; if ((long long)mid * mid n) { left mid 1; } else { right mid - 1; } } return right; }注意我把mid * mid强转成了long long因为当 n 很大时比如 2^31 - 1mid 的平方会超出 int 范围。这种二分答案的应用极其广泛比如在 D 天内运完所有货物求最小运载能力、把数组分成 m 段求各段和最大值的最小值等经典题目都是先猜到答案是某个单调函数的零点然后用二分逼近。二分答案的优点在于只要你能写出一个给定答案判断是否可行的函数通常叫 check 函数就能把复杂的优化问题转化为简单的判定问题。这个思路我在实际项目中处理过类似调度问题非常实用。4.4 浮点数二分与精度控制当答案是实数时二分依然有效只是终止条件从left right变成了right - left eps或者固定迭代次数。double floatBinarySearch(double left, double right) { for (int i 0; i 100; i) { double mid (left right) / 2; if (check(mid)) { left mid; } else { right mid; } } return left; }浮点数二分的几个经验不要用right - left 1e-6这种精度判断因为不同的数据范围对精度的要求差异很大。建议直接固定迭代 100 次这样能保证精度远高于 1e-30而且不会死循环。浮点数没有溢出问题直接用(left right) / 2即可。注意 check 函数的单调性必须自己保证这是二分答案的前提。5. 跳出教科书二分查找在真实项目里的几个妙用5.1 STL 与标准库里的二分写 C 的应该都知道 STL 提供了binary_search、lower_bound、upper_bound、equal_range这四个二分相关函数。我见过不少开发者不知道binary_search只返回 bool 值不能告诉你元素位置于是走了弯路。正确的用法是只判断在不在用binary_search要拿位置用lower_bound/upper_bound要查区间用equal_range。Python 标准库的bisect模块同样提供了bisect_left和bisect_right用法和 C 的 lower_bound/upper_bound 基本一致。建议不管用什么语言把标准库的二分函数用熟写出来的代码不仅健壮而且可读性远高于自己造的轮子。5.2 数据库索引与 B 树二分的亲戚很多人不知道数据库的 B 树索引虽然看起来和二分查找没什么关系但它本质上是多路二分的扩展。B 树每个节点有多个关键字节点内部的查找用的就是二分查找树层与层之间的跳转则是把范围缩小到某个子树的过程思想和二分查找如出一辙。理解这一点对你的实际帮助是当你在数据库里对索引列做等值查询时能预期到它的时间复杂度大约是 O(log n)B 树的层数就是 log 级别的但因为节点可以容纳大量关键字实际层数非常小比如亿级别数据通常只要三四层。当你做范围查询时利用索引的有序性配合二分定位起始位置然后顺序扫描。这些原理性知识能帮你更好地设计表结构和查询语句。5.3 git bisect用二分定位代码回归最后分享一个我日常开发中经常用到、但很多同事都不知道的工具git bisect。它的原理就是标准二分查找目的是在 Git 提交历史里快速定位哪个 commit 引入了 bug。用法很简单git bisect start git bisect bad # 当前 commit 有问题 git bisect good commit-id # 某个历史版本没问题然后 Git 会自动切换到中间某个 commit你测试这个版本有没有问题有问题就执行git bisect bad没问题就执行git bisect good。重复几次Git 就能精确定位到第一个引入 bug 的提交。假设你的项目最近三个月有 1000 个提交用线性排查可能要几天用git bisect只需要大约 10 次测试。这个工具是我在工作里用得最频繁的二分思想实际应用值得每一个开发者熟练掌握。6. 写到最后二分查找不难难的是每个细节都心里有数如果把这篇内容压缩成几句可以带走的话我想告诉你二分查找的框架很简单但魔鬼全在细节里。左闭右闭还是左闭右开还是mid要不要加一这些不是哪种写法更高深的问题而是你必须从头到尾保持一致、并且在写之前就想清楚的约定。每次写完二分相关代码用两个元素的边界 case 走一遍花不了三十秒却能帮你躲掉绝大多数死循环。我个人在这几年的工程实践和面试别人过程中最大的体会是能把二分查找一次写对的人通常不是背熟了模板而是真正理解了区间的含义和收缩的逻辑。理解这点比记住十个模板都管用。希望这篇讲得够透能让你在下次遇到看似要用 O(n) 但实际可以二分的场景时条件反射般地想到它。