1. 为什么说二分查找是“看似简单实则暗坑最多”的算法如果你去问一个刚学编程的人“会不会写二分查找”大概率会得到“这有什么难的”这样的回应。确实二分查找的核心思想一句话就能讲完在一个有序数组里每次砍掉一半的搜索范围直到找到目标值。但如果你真的动手去写尤其是要处理边界条件、重复元素、浮点数精度这些问题时就会发现里面全是坑。我见过不少工作了三五年的工程师在面试手写二分查找时依然会栽在边界处理上。这个算法值得复盘不只是因为面试常考而是因为它是很多复杂算法的基础模块。比如说在有序矩阵中查找、求平方根、搜索旋转排序数组、计算“第一个坏版本”底层都是二分查找的变体。甚至很多看似和“查找”无关的问题比如求一个函数在单调区间内的零点、在有序数据里找分界点最终都能转化成一个二分问题。这篇文章适合这三类读者正在准备算法面试的求职者、参加编程竞赛的学生、以及工作中需要处理大数据量检索但不想用暴力遍历的工程师。我会从最基础的原理讲起把三种常见的区间写法拆开揉碎再结合实际场景讲变体和坑点。你可以把这篇当作一份“二分查找避坑指南”来用。关于标题里的“复盘”两个字我想多说一句复盘不是把代码再抄一遍而是把为什么这么写、边界为什么这样处理、死循环到底是怎么产生的这些问题彻底想明白。这才是这篇博文真正想做的事情。2. 二分查找的核心思路与本质2.1 从“猜数字游戏”理解二分查找的本质想象一个场景朋友让你猜一个1到100之间的数字每次猜完他会告诉你“大了”还是“小了”。最笨的方法是1、2、3挨个试最多要猜100次。但聪明人一定是从50开始猜如果大了就猜25小了就猜75每次都把范围缩小一半。这样最多只需要7次就能猜中。为什么是7次因为100连续除以2到小于1需要7次左右。这个“每次都缩小一半”的思路就是二分查找的本质。这个猜数字的过程之所以高效最重要的一点是每一次比较都能获得足够的信息量。你猜50的时候朋友说“小了”你不仅知道50不是答案还知道1到49全都不可能是答案。一次比较排除了整整一半的可能。这种“排除法”思维是二分查找区别于线性扫描的核心。从数学角度看二分查找的时间复杂度是O(log n)。对数级别的复杂度意味着什么当数据量从1000增长到10亿时线性查找的代价会增长一百万倍而二分查找只需要从10次增加到30次。这种“指数级的数据量增长只带来线性级的代价增加”的特性使得二分查找成为处理大规模数据不可或缺的工具。2.2 三个必须满足的前提条件很多初学者容易忽略二分查找的适用前提导致代码跑起来莫名奇妙。总结下来二分查找要成立必须满足以下三个条件第一数据必须有序。这一点最直观。如果数组本来就是乱的你凭什么判断目标值在左半边还是右半边排序是二分查找的前置操作这也是为什么很多算法题会先让你排序再谈查找。第二数据必须支持随机访问。也就是说你必须能在O(1)时间内拿到任意下标对应的值。数组满足这个条件但链表不满足。如果你拿一个链表去二分每次取中间节点都要从头遍历复杂度直接变成O(n log n)还不如直接线性扫一遍。要注意像Java里的ArrayList可以二分LinkedList就不行。第三查找方向必须满足单调性。二分查找本质上依赖于“目标值在一个方向上必然存在在另一个方向上必然不存在”的单调逻辑。实际应用中有些问题看似不是“查找某个值”但只要存在单调性比如“第k个坏版本”“第一个大于x的位置”就可以用二分来解。这个思维转换非常关键。2.3 时间复杂度的直觉理解很多人对O(log n)的理解停留在“很快”这个层面但“快多少”又说不清楚。这里给一个直观的对比线性查找100万条数据最坏情况下要比较100万次二分查找100万条数据最多只需要比较20次因为2的20次方约等于104万。换句话说二分查找的20次比较就能达到线性查找100万次的效果。在真实业务场景中如果某个查询接口QPS很高把内部实现从线性扫描改为二分查找性能提升是非常夸张的。我调优过一个短字符串列表的匹配服务数据量大概50万条原来遍历一次要几十毫秒改成二分后降到微秒级别——整个服务的瓶颈瞬间从CPU转移到了网络IO上。当然二分查找也有天花板。它要求数据在内存中连续存储对于海量数据来说内存瓶颈可能比查找效率更先出现。这时候就需要考虑B树、跳表这类索引结构了。但从算法学习的角度二分查找是所有后续查找算法的基础这个基础扎实了后面学什么都快。3. 三种主流写法深度拆解闭区间、左闭右开、开区间3.1 标准闭区间写法最推荐也最容易理解闭区间写法即每次搜索的范围是[left, right]左右端点都包含在查找范围内。这是最经典、也最不容易出错的一种写法我强烈建议初学者用它作为默认模板。// 标准闭区间二分查找C实现 int binarySearch(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { // 注意这里是 因为[left, right]是有效区间 int mid left (right - left) / 2; // 防溢出写法 if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid 1; // target在右半部分收缩左边界 } else { right mid - 1; // target在左半部分收缩右边界 } } return -1; // 数组中不存在target }这段代码里有几个关键细节值得反复琢磨循环条件为什么是left right而不是left right因为在闭区间中当left right时区间内还有一个元素这个元素还没有被检查过所以循环必须继续。如果写成最后的那个元素会被漏掉。left mid 1和right mid - 1是做什么的当nums[mid] ! target时mid这个位置已经被排除了所以下一轮搜索区间不应该再包含它。闭区间的收缩边界必须跳过mid否则可能出现死循环——尤其是当left和right相邻的时候若不跳过mid新的区间永远不会缩小。为什么用left (right - left) / 2而不是(left right) / 2这是一个经典的整数溢出问题。当left和right都很大时比如接近INT_MAX两者相加可能超过int的表示范围导致溢出变成负数。而left (right - left) / 2先算差值再除以2就完全规避了这个风险。我用一个例子带大家走一遍流程。假设数组是[1, 3, 5, 7, 9, 11]目标值是7初始left0right5mid2nums[2]5 7所以left3第二轮left3right5mid4nums[4]9 7所以right3第三轮left3right3mid3nums[3]7命中返回3。整个过程只比较了3次非常高效。3.2 左闭右开写法理解它是理解C STL的关键左闭右开区间[left, right)是C标准库中使用最广泛的区间表示方式各大容器迭代器、std::lower_bound都基于这种写法。理解它能让你更容易看懂STL源码。// 左闭右开区间版本C实现 int binarySearchLeftOpen(vectorint nums, int target) { int left 0, right nums.size(); // 注意right是nums.size()不是size-1 while (left right) { // left right时区间为空 int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid 1; // mid被排除 } else { right mid; // 注意这里rightmid不是mid-1因为右边是开区间 } } return -1; }左闭右开写法有几个容易混淆的地方循环条件是left right而不是。因为当left right时区间[left, right)已经是空区间不需要再进入循环。右侧收缩时为什么是right mid而不是right mid - 1因为右边界是开区间right本身不包含在查找范围内。当nums[mid] target时mid虽然被排除了但mid - 1这个位置并未被检查所以right只需要收缩到mid即可。这个细微差别如果不注意很容易在实现lower_bound时出错。初始right为什么是nums.size()而不是nums.size() - 1因为右边界是开区间必须指向最后一个有效元素的下一个位置区间才是完整的。这是“左闭右开”这套约定在C中最核心的规则。这套区间语义理解透了之后你会发现它能统一解决很多问题。比如遍历一个数组for(int i 0; i n; i)本质就是在遍历[0, n)区间。STL中的begin()和end()也是同一个套路end()指向的是最后一个元素之后的位置。3.3 开区间写法第三种选择理解即可开区间写法(left, right)在实际中用得较少但它有助于彻底理解二分查找的边界本质。在这种写法中left和right都不包含在查找区间内。// 开区间版本C实现 int binarySearchOpen(vectorint nums, int target) { int left -1, right nums.size(); // 哨兵元素分别在最左边的前一位和最右边的后一位 while (left 1 right) { // 区间不为空的条件 int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid; // mid被排除后作为新的左边界 } else { right mid; // mid被排除后作为新的右边界 } } return -1; }开区间写法的特点是左右收缩时都不需要加1或减1因为mid本来就处于区间之外。循环条件left 1 right确保中间至少还有一个未检查的元素。我个人建议不要用开区间写法作为主力模板因为它的“哨兵位”思维把left初始化为-1对初学者不太友好。但理解它有助于消除对二分查找的恐惧——你会发现无论哪种区间写法本质上都是在维护“有效搜索区间”边界处理方式只是区间语义的必然结果。3.4 三种写法的对比与选型建议写法区间语义循环条件左侧收缩右侧收缩初始right适用场景闭区间[left, right]left rightleft mid 1right mid - 1size - 1普通查找面试推荐左闭右开[left, right)left rightleft mid 1right midsize与STL对齐lower_bound开区间(left, right)left 1 rightleft midright midsize理解原理特定题型选型建议很简单如果你是初学者或者准备面试直接用闭区间写法如果你平时写C需要和STL库函数打交道一定要掌握左闭右开写法。开区间写法可以等前面的都熟练掌握后再用来加深理解。无论你选择哪种写法最重要的一点是一套代码从头到尾只用一种区间语义千万不要混着来。我见过大量bug的根源就是初始化时用了闭区间的right size - 1循环里却用了左闭右开的while (left right)最后搞出一个诡异的死循环或者越界访问。4. 规避死循环与边界问题核心难点全解析4.1 死循环的本质原因区间无法缩小很多人写二分查找时都遇到过死循环程序卡在那里不动CPU飙到100%。这个问题的根源往往是在某种条件下新的搜索区间和旧搜索区间完全一样导致循环永远退不出去。最经典的一个错误写法在闭区间二分中如果用left mid而不是left mid 1来收缩左边界当区间缩小到[left, right]且left和right相邻时mid left (right - left) / 2会等于left。此时如果nums[mid] target执行left mid后新区间还是[left, right]没有任何变化——死循环诞生了。要避免这个问题只需要记住一条黄金法则在收缩区间时必须保证新区间严格小于旧区间。具体到闭区间写法就是left mid 1、right mid - 1左闭右开写法就是left mid 1、right mid——后者虽然没减1但因为是开区间所以区间大小也在缩小。4.2 整数溢出与负数取整的坑前面提到过mid left (right - left) / 2可以防止溢出。但在某些语言中负数除法的取整方向可能导致意想不到的问题。比如在C中-3 / 2 -1向零取整而-3 1 -2向下取整。如果你的mid计算使用了右移操作而left - right可能为负就会出现取整方向不一致进而导致边界行为异常。所以我会尽量用left (right - left) / 2而不是(left right) 1尤其是在下标可能为负的场景。还有一个经常被忽略的问题right的初始值在某些题目中可能不是size - 1而是size本身比如找插入位置时。这种情况下nums[mid]可能访问到nums[size]直接越界。所以在写二分时一定要对right的语义保持清醒并且在调试时特别关注mid是否可能超出数组边界。4.3 处理重复元素找到第一个/最后一个等于target的位置经典的二分查找只回答“目标值在不在数组里”但实际业务和面试中经常要求返回第一个等于target的下标或者返回最后一个等于target的下标。这就是lower_bound和upper_bound要解决的问题。找第一个等于target的位置本质是在有序数组中找一个位置使得该位置前面所有元素都小于target该位置及其后面的元素都大于等于target。用左闭右开写法可以实现如下// 返回第一个 target 的位置即 lower_bound int lowerBound(vectorint nums, int target) { int left 0, right nums.size(); while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; // mid太小收缩左边界 } else { right mid; // mid target收缩右边界注意不跳过mid } } return left; // 此时left right就是第一个target的位置 }关键点在于当nums[mid] target时不能直接返回mid因为mid左边可能还有等于target的元素。所以只能把右边界收缩到mid继续在左边找。循环结束后left就是答案。同理要找到第一个大于target的位置也就是upper_bound只需要把判断条件从nums[mid] target改为nums[mid] target即可。这两个函数用好了处理“重复元素的查找”就变得非常轻松第一个等于target的位置lowerBound(nums, target)最后一个等于target的位置lowerBound(nums, target 1) - 1target出现的次数upperBound(nums, target) - lowerBound(nums, target)这些都是把二分查找从“会写”提升到“会用”的关键一步。4.4 浮点数二分精度控制与迭代次数二分查找不仅能处理整数数组还能处理浮点数域上的查找问题典型的如“求平方根”“求方程的根”。和整数二分最大的区别是浮点数二分没有“相等”的概念只有“足够接近”。具体来说有两种方法控制浮点数二分的终止条件方法一固定迭代次数。比如迭代100次因为每次区间减半100次之后精度已经远超double的表示能力可以认为结果收敛。这种方法最简单、最稳妥不会因为精度设置不当导致死循环。我个人的习惯是迭代log2((right - left) / precision)次或者干脆固定100次。方法二设置精度阈值。当right - left 1e-7时停止循环。但要注意精度阈值不能设得太小否则可能出现死循环。另外浮点数的舍入误差也可能导致区间缩小到一定范围后无法继续缩进。一个典型的浮点数二分代码如下// 求平方根使用浮点数二分 double sqrtBinary(double x) { double left 0, right max(1.0, x); // 注意x可能小于1 for (int i 0; i 100; i) { double mid (left right) / 2; if (mid * mid x) { left mid; } else { right mid; } } return (left right) / 2; }这里的right初始值设为max(1.0, x)是因为当x 1时比如x0.25平方根是0.5它比x大所以右端点至少要从1开始。4.5 调试二分查找的实战技巧二分查找的bug往往隐藏在各种边界条件中肉眼很难发现。我自己调试时有一套固定的方法第一打印每一轮的left、right、mid。不要嫌日志多死循环问题几分钟就能定位出来。我一般会加这样一段调试代码cout left left , right right , mid mid endl;第二重点测试边界场景。例如数组长度为空、只有一个元素、目标值在开头、目标值在结尾、目标值不存在、目标值小于所有元素、目标值大于所有元素。这些case覆盖到了核心逻辑基本就稳了。第三用“二分的不变量”来验证代码。闭区间写法的核心不变量是“target一定在[left, right]范围内”每次循环结束后都检查一下这个不变量是否成立。如果不成立说明边界收缩写错了。5. 二分查找的经典变体与应用场景5.1 从“找一个数”到“找一个区间”搜索旋转排序数组经典的二分查找要求数组完全有序但真实场景中数据往往具备部分有序的特征。最典型的就是“旋转排序数组”问题一个升序排列的数组在某个未知位置发生了旋转比如[4, 5, 6, 7, 0, 1, 2]要求在O(log n)时间内找到目标值。解决思路是虽然整个数组不是全局有序但任意一个mid位置必然有左半部分或右半部分是全局有序的。具体判断方法是如果nums[left] nums[mid]说明左半部分有序可以判断target是否在[nums[left], nums[mid]]区间内从而决定收缩方向否则右半部分有序同理判断。这个变体考察的核心不是二分本身而是如何利用部分有序性来缩小搜索区间。面试中出现频率非常高建议多写几遍直到不需要看参考代码。5.2 二分答案把“求解问题”转化为“判定问题”二分查找还有一个非常强大的用法叫“二分答案”。有些问题要求“最小化最大值”或“最大化最小值”这时候如果直接求解很难但可以从答案的范围入手用二分枚举答案再验证某个答案是否可行。最典型的例子是“分割数组的最大值”问题给定一个数组和一个整数m把数组分成m个连续子数组要求每个子数组的和的最大值最小。思路是答案一定在[max(数组中的最大值), sum(整个数组)]之间。对答案做二分每次用一个贪心的判定函数检查“是否能分成不超过m个子数组且每个子数组和都不超过mid”。如果可行说明mid还可以再小否则需要增大mid。这个思路把“求解”变成了“判定”在竞赛算法和面试中都非常常见。我甚至可以说掌握了“二分答案”这个思维模式很多看似毫无头绪的问题都能找到切入点。5.3 工程领域中的二分思想接雨水、搜索二维矩阵、求解器中的对分法二分查找在工程领域的应用比大多数人想象得要广。第一个例子是“搜索二维矩阵”一个矩阵每行从左到右递增每行第一个数大于上一行最后一个数这其实可以完全展开成一个有序数组做二分。即使不满足这种强有序条件只要矩阵的某一行和某一列分别有序也可以用“从右上角开始比较”的线性二分思路一次排除一行或一列。第二个例子是数值计算中的“二分法求根”。在工程软件中很多非线性方程的求解会先用二分法在区间内缩小区间再用牛顿法加速收敛——因为二分法虽然慢但一定收敛牛顿法虽然快但不一定稳定。两者结合是最经典的一种稳健策略。第三个例子是硬件设计中的二分思想。搜索热词里出现了“fpga二分查找树编码器”在硬件查找表LUT的设计中二分查找树结构被用来加速匹配和编码过程。这里的核心思路和软件二分完全一致只是换了一套语言描述——每次比较的输出决定走树的左分支还是右分支。软件二分里mid的计算对应到硬件里就是比较器阵列的布局软件里的循环对应到硬件里就是流水线中的每一级。这种跨领域的类比很有意思能帮你看出二分查找本质上是“用比较换信息量”的通用策略。5.4 二分查找与其他算法思想的组合二分查找很少单独出现它经常和其他算法组合使用形成复合解法。比如二分 贪心上面提到的“分割数组的最大值”就是这么解决的。贪心负责“验证是否可行”二分负责“枚举最优答案”。二分 前缀和在需要频繁查询区间和的问题中二分定位边界后用前缀和快速计算区间和能把复杂度从O(n)降到O(log n)。二分 单调栈/单调队列某些滑动窗口问题窗口的滑动或最优解的选择满足单调性可以配合二分快速定位。二分 DP有些动态规划问题状态转移中的最优分割点具有单调性可以用二分优化决策过程。这属于较高级的DP优化技巧但底层依赖的仍然是“单调性 快速定位”。可以说二分查找是很多高级算法的“基础设施”。基础不打牢后面学这些组合套路时就会很吃力。6. 常见问题与排查技巧实录6.1 问题速查表现象可能原因解决方案死循环程序不退出边界收缩时没有跳过mid比如leftmid或rightmid闭区间用leftmid1、rightmid-1左闭右开用leftmid1、rightmid返回-1但目标值明明存在循环条件写错比如闭区间用了left right闭区间用while (left right)数组越界right初始值设置错误或mid计算超出数组范围确认right是size-1还是size在访问nums[mid]前打印检查返回的下标不对偏左或偏右在重复元素场景没有区分lower_bound和upper_bound先明确需求是“第一个”还是“最后一个”再选择收缩策略浮点数二分陷入死循环精度阈值设置过小或者区间缩小到浮点精度极限改用固定迭代次数如100次旋转数组查找结果错误没有判断左右哪一部分有序直接套普通二分先判断哪半部分有序再决定收缩方向二分答案时判定函数写错贪心验证的规则有问题导致二分收敛到错误结果先单独写一个测试函数验证判定函数在不同mid下是否正确6.2 我踩过的几个坑第一个坑是刚开始学的时候总喜欢把mid设置为(left right) / 2结果在数组很大的时候出现溢出返回负数导致越界。当时排查了很久才发现是这个问题。后来就形成了条件反射写二分第一行就写mid left (right - left) / 2。第二个坑是在处理“查找第一个等于target的位置”时用闭区间写法实现代码越写越复杂各种if嵌套最后还是错的。后来切换到左闭右开写法逻辑瞬间清晰了。这让我意识到不同的查找变体可能适合不同的区间语义。做lower_bound这类问题首选左闭右开做普通查找首选闭区间。不用强迫自己用一种写法解决所有问题。第三个坑是在浮点数二分中把终止条件写成了while (right - left 1e-10)结果在求某些特殊值比如非常大或非常小的浮点数时陷入死循环。原因是double的精度有限当区间小到一定程度后right - left可能因为舍入误差而无法继续缩小到小于阈值。从那以后我处理浮点数二分一律用固定迭代次数省心又稳定。6.3 一个排查实录STL的lower_bound为什么返回了很奇怪的结果有一次我在项目里用std::lower_bound查询一个有序容器的插入位置结果返回的位置和我预期的不一样。排查了很久最后发现原因不在lower_bound本身而是我在调用之前的排序规则和lower_bound的比较规则不一致。std::lower_bound默认使用operator进行比较也就是升序比较。如果我的容器用了自定义的降序排序规则却没有给lower_bound传入对应的比较器它就会按照升序规则去查找结果自然不对。这个案例提醒我二分查找的正确性不仅依赖于代码本身还依赖于数据有序性的定义方式。排序规则和查找规则必须保持完全一致。在实际工程中当“有序”的定义比较复杂比如按结构体的某个字段排序这个坑就特别容易踩到。7. 总结与延伸思考从面试笔试到工程应用二分查找渗透在算法领域的方方面面。复盘这个算法时我个人的体会是真正的关键不在于背模板而在于理解区间边界的变化逻辑和不变量的维护。模板可能被忘记但只要理解了“为什么”“为什么mid 1”“为什么right mid”任何时候都能重新推导出正确的代码。如果你想继续深入建议按这个顺序练习先掌握闭区间写法的标准二分查找再掌握lower_bound和upper_bound学会处理重复元素然后练习二分答案的思维做一些“最大值最小化”类的题目最后挑战旋转有序数组、二维矩阵查找等变体。我自己在面试别人时最看重的是候选人能否清楚地解释边界条件的推导过程。能说清楚“为什么这里用而不是”的人通常说明真的理解了二分查找而不是死记硬背。希望这篇复盘能帮你到达那个状态。