二分搜索全解析：从循环不变量到工程实践

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 闭区间、开区间：两种写法的完整对比

我先把两种常见写法的差异列出来，你再跟着我推导一遍，就能明白区别的本质。

你会发现，闭区间的循环结束条件是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 + 1，mid向下取整没问题。因为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 })

Python：

import 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。

这个问题你怎么想？最笨的方法是从k=1开始试到最大堆的数量，检查每个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 = mid，left = 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 > eps，eps是你需要的精度，比如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的移动会不会让区间始终缩小？把这三个问题想清楚，代码自然就写对了。希望这篇文章能帮你建立同样的思维习惯。