1. 为什么我建议每个开发者都彻底搞懂二分搜索先说结论二分搜索Binary Search这个算法刷题要考工作要用而且它背后的思维模式会改变你写代码的方式。很多人觉得二分搜索就是“在一个有序数组里找一个数”代码几行就写完了没什么好学的。但实际上我面试候选人时发现能一遍写对二分搜索的人不到三成。不是大家不会而是边界条件、循环不变量、退出时机这几个东西只要有一个想不清楚就会写出死循环或者越界的代码。更别说二分的变体比如找左边界、找右边界、在旋转数组里搜索、在实数范围内逼近答案这些场景一旦展开很多人的模板就失灵了。这篇文章我想从底层原理讲到工程实战把二分搜索的来龙去脉掰开揉碎。适合正在刷算法题准备面试的人也适合想提升代码能力的在职开发者。我不打算只给你一个模板而是想让你理解这个模板是怎么来的这样不管题目怎么变你都能自己推导出正确的写法。1.1 一切要从“猜数字”说起你先想一个场景朋友在1到100之间选了一个数你每次猜一个数对方告诉你“大了”还是“小了”你要用最少的次数猜中。最优策略是什么先猜50。如果大了目标就在1到49之间如果小了目标就在51到100之间。无论哪种情况你都把问题规模缩小了一半。再在剩下的区间里取中间值继续猜这样最多猜7次就能命中因为2的7次方是128覆盖了100个数字。这就是二分搜索的核心思想每次排除掉一半的不可能区域把O(n)的线性查找变成O(log n)的对数查找。n是100时差别还不明显n是10亿时线性查找要10亿次二分搜索只要30次。这个差距是质变不是量变。很多人觉得二分搜索简单是因为他们只看到了“在有序数组里查找”这个具体应用。但二分的本质不是“数组有序”而是“单调性”三个字。只要有单调性就能二分。1.2 适用前提单调性才是二分搜索的灵魂我换个方式问无序数组能用二分吗不能因为无法判断舍弃哪一半。为什么有序就能判断因为有序数组满足一个关键性质如果中间值已经大于目标值那么中间值右边的所有值也都大于目标值所以右边这一半可以整体丢弃。这个“如果A成立那么A的右边全部成立”的性质就是单调性。工程中很多问题看似和“有序数组”无关但只要你能找到一种“单调的判定函数”就能用二分来加速。举个例子你要找满足某个条件的最小值。如果这个条件本身具有单调性——值越大越容易满足条件或者值越小越容易满足条件——那么你就可以在解空间里做二分。这种用法有个专门的称呼叫“二分答案”后面我会详细展开。先把概念记住二分搜索真正依赖的是单调性不是“数组长得好不好看”。1.3 二分搜索能解决的问题全景先给你一张全景图后面会逐个展开在有序数组中查找目标值最基础的形式。查找目标值的左边界或右边界用于统计重复元素的范围。在旋转有序数组中查找目标值经典变体考察对二分边界的掌控。实数范围内的二分搜索比如求平方根、求满足精度要求的方程解。二分答案把“求最优值”转化为“在解空间里做判定”广泛应用于贪心和动态规划类问题中。二叉搜索树的查找、插入、删除本质是二分思想在树结构上的体现。对分查找算法导论、C STL的lower_bound/upper_bound、Java的Arrays.binarySearch都是二分搜索的标准实现。这些场景的共同点是都有一个单调的搜索空间并且我们希望通过每次排除一半来快速逼近答案。2. 一个模板吃透边界从循环不变量推导正确写法写二分搜索最难的不是思路是边界。while (left right)和while (left right)到底有什么区别mid到底取整数除法还是向上取整left mid还是left mid 1这些问题的答案都不应该靠背而应该靠“循环不变量”来推。我带你走一遍完整的推导过程以后不管题目怎么变你都能自己写对。2.1 先说为什么要用“循环不变量”来思考循环不变量loop invariant这个名词听起来唬人说白了就是在循环开始前、循环中、循环结束后始终成立的一个条件。你只要保证这个条件在每轮循环时都保持成立算法就不会出错。对于二分搜索我先选定一个区间定义搜索范围是闭区间[left, right]表示目标值只可能存在于这个区间内而且这个区间始终是有效的。这个“目标值在闭区间内”的断言就是我的循环不变量。有了这个不变量三件事就能被推导出来第一循环什么时候结束当left right时区间为空里面不可能有目标值循环就该停了所以条件是while (left right)。第二检查完mid后怎么收缩如果nums[mid] target说明目标值在右边那么新区间应该是[mid 1, right]因为mid已经被排除了如果nums[mid] target说明目标值在左边新区间是[left, mid - 1]如果相等直接返回。第三循环结束后left 和 right 的含义是什么循环结束时left right而且如果没找到目标值left恰好指向“第一个大于等于目标值的位置”right指向“最后一个小于目标值的位置”。这个性质后面找左右边界时会用上。2.2 闭区间、开区间两种写法的完整对比我先把两种常见写法的差异列出来你再跟着我推导一遍就能明白区别的本质。写法区间定义初始化循环条件mid 排除方式循环结束时区间闭区间[left, right] 包含两端left0, rightn-1left rightleft mid1 或 right mid-1left right区间为空左闭右开[left, right) 包含左端不含右端left0, rightnleft rightleft mid1 或 right midleft right区间收敛到一点你会发现闭区间的循环结束条件是left right而左闭右开的结束条件是left right。这个区别会导致一个经典问题如果左闭右开写right mid - 1就会漏掉元素或造成死循环。每种写法必须配套相应的区间收缩方式不能混用。有人问哪种写法更好我的建议是初学者牢牢记闭区间写法因为它的循环不变量最直观“区间里还有没有元素”一眼就能判断。刷题多了以后可以再掌握左闭右开因为很多标准库函数用了这种写法比如C的lower_bound、Go的sort.Search。2.3 mid 的取法一个两行代码引发的血案先看一个几乎所有教材都会告诉你的写法int mid (left right) / 2;这个写法有什么问题当left和right都接近整数上限时left right会溢出。比如left和right都是2的30次方级别一加就直接变成负数了mid算出来是错的二分直接崩。正确的打开方式是int mid left (right - left) / 2;这样把加法变成了减法永远不会溢出。这行代码看起来不起眼但在生产环境里处理大数组时它真的能救命。我在面试时遇到过候选人用第一种写法当我问“left和right都是int最大值附近会怎样”时他立刻反应过来了。这个细节很能反映一个人是否真正写过大规模数据。那mid要不要加1呢这取决于你怎么收缩区间。在闭区间写法里mid left (right - left) / 2是向下取整。当区间长度为偶数时mid偏左。比如[0, 5]mid是2。当区间只剩两个元素时比如[2, 3]mid是2。这个偏左的特性在有些情况下会导致死循环比如当你写left mid而不是left mid 1时。怎么判断该不该给mid加1记住一条经验法则如果区间收缩方式是left mid那么mid必须向上取整写成left (right - left 1) / 2如果收缩方式是left mid 1mid向下取整没问题。因为left mid意味着mid至少要比原来的left大1区间才有进展否则就会原地打转。2.4 返回值的语义要提前想清楚很多二分变体的难点在于不是要你“找到目标值”而是要你“找到目标值应该插入的位置”或者“找到第一个大于等于目标值的元素”。这时候返回left还是right还是mid是有讲究的。基于闭区间写法循环结束时left right 1目标没找到时left指向第一个大于等于target的位置。这个语义就是lower_bound。right指向最后一个小于target的位置。所以如果你要实现lower_bound循环结束后直接返回left就行。如果你要实现upper_bound第一个大于target的位置可以在nums[mid] target时移动left最后返回left。这里就不一步步展开了下文讲左右边界时会给出完整的代码。你现在只需要记住二分写完后left和right是有语义的不是随机数它们指向的位置能告诉你很多信息。3. 从标准库到工程实践二分搜索的真实用法理论推导完了接下来看实际工程里的二分搜索。你会发现不同语言的标准库都有自己的二分实现但细节各不相同。这一节我把它们都拉出来对比一下再教你写自己的版本。3.1 标准库中的二分搜索实现对比先看几个主流语言的标准库C STL// 返回第一个 value 的迭代器 auto it std::lower_bound(nums.begin(), nums.end(), value); // 返回第一个 value 的迭代器 auto it std::upper_bound(nums.begin(), nums.end(), value);Java// 直接二分查找找不到返回负数插入点取反减1 int idx Arrays.binarySearch(nums, target);Go// 返回 [0, n) 中第一个使 f(i) 为 true 的下标 idx : sort.Search(n, func(i int) bool { return nums[i] target })Pythonimport bisect # 分别对应 lower_bound 和 upper_bound left bisect.bisect_left(nums, target) right bisect.bisect_right(nums, target)你有没有注意到它们的共性标准的库函数基本都实现了“在升序序列里找边界”的语义而不是“找到任意一个相等元素”。这是有道理的——因为“找到任意一个相等元素”这个语义在工程里非常局限而“找一个边界”能覆盖更多场景统计重复次数、找插入位置、求前驱后继全都能用。我自己在工程里很少手写二分基本都是用标准库因为标准库代码经过千锤百炼边界处理比我临时写的要可靠。但前提是我必须清楚它返回的语义。比如Java的Arrays.binarySearch找不到时会返回-(insertionPoint) - 1很多人记成-insertionPoint结果解插入位置的时候错了。这种细节其实就是二分搜索在工程中最常见的坑。3.2 自己实现一个不踩坑的 lower_bound 和 upper_bound如果你需要自定义比较逻辑比如按对象的某个字段查找标准库可能就不够用了这时候你要自己写。我推荐你背下的版本是// 在升序数组 nums 中找到第一个 target 的下标 int lowerBound(int[] nums, int target) { int left 0, right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return left; }这个版本关键点在于当nums[mid] target时我们不直接返回mid而是把right收缩到mid - 1继续往左边找。循环结束时left指向第一个不小于target的位置。这个逻辑等价于找到“满足条件的最小下标”。相应的upperBound是第一个大于target的位置int upperBound(int[] nums, int target) { int left 0, right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return left; }仔细对比这两个函数唯一的区别在于等于target时如何处理。这个区别就是lower_bound和upper_bound的本质差异。我建议你在草稿纸上跑一个例子比如nums [1, 2, 2, 2, 3]手动模拟一遍体会left如何一步步逼近第一个2和第一个3的位置。有了这两个函数统计某个值在数组里的出现次数就很简单了upperBound(nums, target) - lowerBound(nums, target)。3.3 二分答案把最优化问题变成判定问题这一节我想单独强调因为它牵扯到二分搜索最强大的应用——二分答案。什么叫二分答案当题目让你求“最大值的最小值”或“最小值的最大值”时如果解空间是单调的你就可以直接在解空间里进行二分。举个例子经典的“吃香蕉”问题有n堆香蕉每堆piles[i]根警卫离开h小时你每小时能吃掉k根如果一堆少于k根你吃完这堆后这一小时内不能吃别的求能在h小时内吃完所有香蕉的最小速度k。这个问题你怎么想最笨的方法是从k1开始试到最大堆的数量检查每个k是否能在h小时内吃完第一个成立的k就是答案。这个检查过程是O(n)外层从1试到max(piles)最差O(max * n)太慢了。但注意一个关键性质k越大越容易在h小时内吃完。也就是说“能否在h小时内吃完所有香蕉”这个判定函数关于k是单调的。那么就可以在[1, max(piles)]这个范围内二分k每次用O(n)的判定函数检查总复杂度O(n log max(piles))。int minEatingSpeed(int[] piles, int h) { int left 1, right 0; for (int p : piles) { right Math.max(right, p); } while (left right) { int mid left (right - left) / 2; if (canFinish(piles, mid, h)) { right mid; } else { left mid 1; } } return left; } boolean canFinish(int[] piles, int speed, int h) { int hours 0; for (int p : piles) { hours (p speed - 1) / speed; // 向上取整的写法 } return hours h; }注意到这里我用的是左闭右开写法while (left right)right midleft mid 1。为什么换写法了因为二分答案的单调性经常是“满足条件的一侧我们都想保留不满足的一侧全部丢弃”。左闭右开写法在这种场景下特别顺手因为right mid天然表示“mid可能是答案所以保留这个可能”而left mid 1表示“mid不可能丢弃”。如果你对这两种写法切换感到混乱我建议你暂时只用闭区间写法也能做只是代码稍微绕一点。重要的是理解每一步的语义而不是死记模板。4. 高频变体旋转数组、浮点数二分和二叉搜索树学完基础肯定要过变体。二叉搜索的变体非常多我挑三个最常出现且最能检验理解的场景来讲旋转排序数组、浮点数二分、以及二叉搜索树中的二分思想。4.1 在旋转有序数组中查找目标值题目是这样原数组是升序的比如[0,1,2,4,5,6,7]从某个未知位置旋转一下变成[4,5,6,7,0,1,2]现在要在这样的数组里查找一个目标值。看似被打乱了但其实有个关键性质旋转后的数组任意从中间切一刀至少有一半是有序的。为什么因为旋转数组本质是“两段升序拼接”mid总能把数组切成左右两半其中必有一半完全落在一段有序序列里。你只要先判断哪一半有序再判断目标值是否在那个有序区间内就能决定舍弃哪一半。int search(int[] nums, int target) { int left 0, right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { return mid; } // 左半部分有序 if (nums[left] nums[mid]) { if (target nums[left] target nums[mid]) { right mid - 1; } else { left mid 1; } } // 右半部分有序 else { if (target nums[mid] target nums[right]) { left mid 1; } else { right mid - 1; } } } return -1; }这个代码要特别注意nums[left] nums[mid]里的等号。当left mid时比如区间只剩两个元素这个等号决定了走哪个分支。漏掉等号有些边界case会出错。另外这个问题还有一个进阶版如果数组里有重复元素nums[left] nums[mid] nums[right]时会无法判断哪一半有序这时候只能暴力地把left和right各收缩一格。重复元素的旋转数组搜索时间复杂度最好O(log n)最坏O(n)这个退化场景要心里有数。4.2 浮点数二分精度控制和收敛判定浮点数二分和整数二分在思路上完全一样但有两个很大的区别没有整数溢出问题取而代之的是精度问题没有“1/-1”的边界收缩取而代之的是直接让left mid或right mid。比如求一个数的平方根double sqrt(double x, double eps) { double left 0, right x; // 为了处理 x 1 的情况right 至少是 1 right Math.max(1, x); while (right - left eps) { double mid left (right - left) / 2; if (mid * mid x) { right mid; } else { left mid; } } return left; }这里没有mid 1因为实数空间里没有“相邻整数”的概念直接把区间缩到一半就行。循环终止条件也不是left right而是right - left epseps是你需要的精度比如1e-7。浮点二分有坑吗有。第一个坑是right的初始值。如果x小于1比如0.04平方根是0.2但right x 0.04那答案0.2根本不在区间里。所以初始区间要确保包含答案常见做法是让right Math.max(1, x)。第二个坑是eps不能设得太小小到超过了浮点数的精度极限就会死循环。double类型下eps设成1e-15以下基本没有意义。我一般用1e-7做输出精度因为题目通常只要求小数点后6位。浮点二分在工程上的应用也很多比如求某个方程的近似解、机器学习里的学习率搜索、图形学里的光线求交只要目标函数是单调的浮点二分就是一个非常稳定的数值求解方案。4.3 二分思想在二叉搜索树中的体现最后提一下二叉搜索树BST它其实就是二分思想的树形化。BST的定义是任意节点的左子树所有节点都小于该节点右子树所有节点都大于该节点。你在BST里查找一个值过程就是二分的投影把当前节点当作mid如果要找的值比它小就去左子树相当于丢弃右半边否则去右子树相当于丢弃左半边。一个有n个节点的平衡BST查找复杂度是O(log n)这跟二分搜索在有序数组里的复杂度一模一样。区别在于数组二分需要先排序并静态存储而BST支持动态插入和删除所以它是“动态二分”的一种实现。删除操作稍复杂一些因为要维持BST性质找到目标节点后如果它有左右两个孩子一般用右子树的最小节点或左子树的最大节点来替代它。这个“替代”就相当于二分搜索里用边界值来填充需要你仔细处理指针关系否则会丢节点。理解了这一点你会发现很多数据结构都是二分思想的变体比如B树、跳表、堆里的某些查找逻辑。二分不是一道算法题而是一类系统性思维方法。5. 常见问题与排查技巧实录这一节我讲点实战中容易踩的坑都是我真实遇到过的。5.1 死循环是怎么发生的死循环是二分搜索最常见的bug尤其出现在区间收缩方式写错的时候。比如这段代码int left 0, right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid; } else { right mid - 1; } }假设nums[mid] target成立且此时left和mid相等left mid相当于没动下一轮循环还是同样的状态死循环就产生了。这就是我之前强调的当你写left mid时mid必须保证比当前left大即向上取整。排查死循环的方法很简单手动模拟只有两个元素的情况。比如nums [1, 3]target 4看看left和right每轮怎么变化。如果发现某一轮left和right都不变基本就是死循环元凶。5.2 mid 溢出和 off-by-one 的排查方式mid溢出上面已经提过这里说两个排查技巧。第一个技巧是打印日志。在循环里输出left、right、mid三个值看它们的变化。如果left和right不收敛或者mid反复出现同一个值说明边界收缩有问题。第二个技巧是针对while (left right)和while (left right)的混淆。如果你发现循环结束时left的位置和预期差1多半是循环条件搞错了。我自己的排查经验是先确定循环结束时left想指向哪里然后倒推条件。如果left想指向“第一个满足条件的位置”那大概率应该用while (left right)配上right mid的写法如果用while (left right)就要格外注意结束时left的语义。5.3 一个“找插入位置”的完整走读我拿LeetCode 35题“搜索插入位置”来走一遍完整流程。题目是给定排序数组和目标值如果找到目标值返回其索引如果没有找到返回它被按顺序插入的位置。用闭区间lower_bound的写法正好解决问题int searchInsert(int[] nums, int target) { int left 0, right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return left; }核心变化在于nums[mid] target时不直接返回而是继续让right mid - 1。这样最后left就是第一个不小于target的位置。如果target存在left就是target本身的下标如果target不存在left就是应该插入的位置。像“在旋转数组中找最小值”“寻找两个有序数组的中位数”“猜数字大小”这些经典题目本质上都是在同一条主线上加变化。我建议你把基础模板吃透后每天挑一两道变体题练手连续一周你的二分功力会有质的飞升。6. 最后再分享一个我在工程里常用的实践技巧二分搜索虽然看起来简单但我在代码评审里见过太多次因为边界写错导致的线上bug。所以我现在养成了一个习惯所有手写的二分逻辑必须配上边界测试用例再合入。我常用的测试用例套路是这几种数组长度为0、长度为1、长度为2、目标值小于所有元素、目标值大于所有元素、目标值等于首元素、目标值等于末元素、目标值连续出现多次。用这几组用例一跑大部分边界问题都能暴露。我有一个印象很深的教训有次在推荐系统的排序服务里我用二分查找某个用户的历史行为分界点因为少写了一个等号导致返回的插入位置偏了1位上线后部分用户的推荐结果错乱。排查了很久才发现就是那一行if (nums[mid] target)和if (nums[mid] target)的区别。这种问题代码不会报错数据也不会丢它只是静默地让你拿到一个错一格的答案。所以二分搜索的正确性真的很依赖你对边界语义的精确把握。也正因为这个经历我后来写二分特别推崇“从语义出发不要从记忆出发”的方式。段落一开始先问自己三个问题这个区间是闭还是半开循环结束时left指向哪里mid的移动会不会让区间始终缩小把这三个问题想清楚代码自然就写对了。希望这篇文章能帮你建立同样的思维习惯。