很多初学算法的朋友应该都有过这种体验：二分查找，看代码的时候觉得逻辑清清楚楚，不就是每次砍一半嘛；可真到了自己动手写，不是while循环条件写错导致死循环，就是边界值没处理好返回了错误的下标。我当年在刷LeetCode 704的时候就被这个"简单题"狠狠教育过一回，debug半天发现是right = mid和right = mid - 1的区别没想明白。
代码随想录里把二分查找放在第一个专题，其实是很有深意的。这个算法看似基础，但它背后牵扯到一个特别重要的编程思维——循环不变量。如果你能把这个弄明白，后面再学二叉树、链表、滑动窗口，很多边界问题都会迎刃而解。这篇文章我就以代码随想录的讲解思路为骨架，加上我自己刷题和实际面试中总结的经验，把这一个知识点揉碎了讲清楚。
1. 二分查找的核心思想与适用边界
1.1 为什么"每次砍一半"能这么快
先来建立一个直观的认知。假设有一个长度为100万的有序数组，你要找某个数。暴力遍历最坏情况下要比较100万次，而二分查找每次比较后都能排除一半的元素：
- 第一次比较，剩50万个候选；
- 第二次，剩25万个；
- 第三次，剩12.5万个；
- ...
- 约20次后，就只剩下1个元素。
这个"每次砍半"的效率就是O(log n)。你可能会发现一个反直觉的点：数组越大，二分查找的优势就越明显。100万个元素只要20次比较，10亿个元素也才30次，这就是对数时间复杂度的威力。
这里有个细节值得注意：二分查找的前提条件很严格——数据必须是有序的，并且是支持随机访问的存储结构（比如数组）。像链表这种只能顺序访问的结构，就算有序也没法用传统二分，因为取中间值本身就要遍历，复杂度退化得很厉害。
1.2 什么时候能用二分查找
很多初学者容易陷入一个误区，认为只有"数组有序"才能用二分。实际上，二分查找的本质是通过单调性进行决策——只要你能构建一个"左半边满足某条件、右半边不满足"的单调序列，就可以用二分去寻找那个分界点。
常见的应用场景有四类：
- 在有序数组中查找指定元素（最基础的用法）；
- 查找第一个/最后一个满足条件的元素，也就是左右边界问题；
- 在值域上进行二分，比如LeetCode 875（爱吃香蕉的珂珂）、LeetCode 1011（在D天内送达包裹的能力），这些题不是直接搜数组元素，而是对"答案"进行二分；
- 在某些单调函数上寻找极值或零点，比如浮点数二分求平方根。
理解了这一点，你就会明白为什么代码随想录会把这个内容放在最前面——它训练的不是"背代码"，而是识别单调性的能力。面试考二分，表面考代码，实际考的是你有没有建立起这个抽象思维。
2. 循环不变量：所有边界问题的根源
2.1 你对区间的定义，决定了代码的一切
我在刚开始写二分查找时，最头疼的就是：while里面到底是left < right还是left <= right？更新边界时到底是right = mid还是right = mid - 1？这些答案并不固定，它们完全取决于你怎么定义"当前搜寻区间"。
代码随想录里反复强调的"循环不变量"，说人话就是：你在写代码前，必须先明确每一轮循环中，搜索范围是一个什么样的区间。一般有两种定义方式：
- 左闭右闭 [left, right]：左右边界都包含在搜索范围内；
- 左闭右开 [left, right)：左边界包含，右边界不包含。
这两种定义在数学上都严格成立，没有谁对谁错。但你一旦选定了一种，代码里所有的边界更新都必须严格遵守这个定义，不能混着来。几乎所有二分查找的bug，都源于区间定义和边界更新的不一致。
为了让你直观感受这个差距，我先把两种写法完整地列出来，下一节再逐行分析。
2.2 版本一：左闭右闭写法
左闭右闭意味着left指向的元素和right指向的元素，都还没有被排除，都属于候选区间。
int binarySearch(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; // 关键1：right 指向最后一个有效元素 while (left <= right) { // 关键2：left == right 时，区间内还有一个元素需要判断 int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; // 关键3：mid已经比较过了，排除它，区间变成 [mid+1, right] } else { right = mid - 1; // 关键3'：排除mid，区间变成 [left, mid-1] } } return -1; }三个关键点的逻辑是一致的：因为区间包含right，所以当left == right时不能退出循环，还要判断这个元素。又因为mid已经被比较过，所以无论走哪个分支，都不能让新区间再包含mid，必须+1或-1偏移掉。
2.3 版本二：左闭右开写法
左闭右开意味着right指向的元素不参与候选，它只是一个"上界"标记。
int binarySearch(vector<int>& nums, int target) { int left = 0; int right = nums.size(); // 关键1：right 指向最后一个元素的下一个位置 while (left < right) { // 关键2：left == right 时区间为空，循环终止 int mid = left + (right - left) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { left = mid + 1; // 关键3：mid已排除，新区间为 [mid+1, right) } else { right = mid; // 关键3'：mid已排除，但新区间要包含左边界，所以 right = mid } } return -1; }注意这里最反直觉的一点：当nums[mid] > target时，更新的是right = mid，而不是right = mid - 1。因为在左闭右开定义下，right本身就不在候选区间里，把right挪到mid的位置，等于把mid和它右边的所有元素都排除了，而[left, mid)这个新区间依然完整且合法。
2.4 两种版本的实际对比
我整理了一个对比表格，方便你快速对照记忆：
| 对比维度 | 左闭右闭 [left, right] | 左闭右开 [left, right) |
|---|---|---|
| 初始right | nums.size() - 1 | nums.size() |
| 循环条件 | left <= right | left < right |
| 收缩左边界 | left = mid + 1 | left = mid + 1 |
| 收缩右边界 | right = mid - 1 | right = mid |
| 空区间判断 | left > right | left == right |
| 数组长度为1时 | 正常进入循环 | 正常进入循环 |
我个人在实际刷题中的体会是：左闭右闭更符合日常直觉，因为大多数人习惯把right当成"最后一个有效下标"来用，写起来不容易懵。但左闭右开在C++的STL里特别常见，比如vector::begin()和end()就是左闭右开的关系，熟悉它对以后理解迭代器很有帮助。
3. 手把手推演一个完整查找过程
3.1 全流程走查：从入口到出口
光看代码还是不够，我建议你像我一样，在初学阶段拿张纸，把每一轮left、right、mid的数值走出来。以数组nums = [1, 3, 5, 7, 9]，查找目标target = 5为例，用左闭右闭版本：
第一轮：left = 0, right = 4，区间[0, 4]。计算mid = 0 + (4-0)/2 = 2，nums[2] = 5，命中，返回2。
这个例子太顺了，看不出边界处理的必要。换一个更刺激的场景：查找target = 6（数组中不存在）。继续用左闭右闭：
- 初始化：
left = 0, right = 4 - 第一轮：
mid = 2，nums[2] = 5 < 6，所以left = mid + 1 = 3。此时区间[3, 4] - 第二轮：
mid = 3 + (4-3)/2 = 3，nums[3] = 7 > 6，所以right = mid - 1 = 2。此时区间[3, 2] - 循环条件判断：
left <= right即3 <= 2为false，退出循环，返回-1。
注意第二轮结束后，left > right，说明这个区间已经"空"了——所有可能的元素都被排除干净，确实找不到6。这逻辑是严丝合缝的。
再看左闭右开版本在同样场景下的表现：
- 初始化：
left = 0, right = 5 - 第一轮：
mid = 2，nums[2] = 5 < 6，所以left = 3，区间[3, 5) - 第二轮：
mid = 3 + (5-3)/2 = 4，nums[4] = 9 > 6，所以right = mid = 4，区间[3, 4) - 第三轮：
mid = 3 + (4-3)/2 = 3，nums[3] = 7 > 6，所以right = mid = 3，区间[3, 3) - 循环条件判断：
left < right即3 < 3为false，退出循环，返回-1。
两种写法的"出口时刻"不一样，但都正确地返回了-1。这就是循环不变量的作用——只要你的逻辑自洽，正确的写法不止一种。
3.2 死循环到底是怎么发生的
很多人在某个版本里会遇到程序卡住不动的情况，这通常就是mid的更新和边界收缩配合失误。最常见的错误写法是在左闭右开版本里把收缩右边界写成right = mid - 1：
- 假设某轮
left = 3, right = 4，区间[3, 4)，只有一个元素3。 mid = 3 + (4-3)/2 = 3，假如nums[mid] > target，按错误写法right = mid - 1 = 2，区间变成[3, 2)——这倒是退出循环了，但跳过了边界检查，有可能漏掉正确答案。- 假如
nums[mid] < target，错误写法left = mid + 1 = 4，区间[4, 4)为空，正常退出，没问题。
这种错误是"隐性错误"，程序不会崩，但结果可能不对。另外一种更棘手的情况是mid的计算方式配合不当导致的死循环——比如在查找右边界时使用了下取整的mid，同时left = mid，就可能在两个相邻下标之间反复横跳。这个坑我在第5节讲边界时专门展开。
我的建议是：初学阶段不要混用，先把左闭右闭练到滚瓜烂熟，再去研究左闭右开。很多人一上来就看多种写法，结果边界规则互相干扰，越学越乱。
4. 从LeetCode 704到PTA函数题：实战对照
4.1 LeetCode 704的原题要求
LeetCode 704这道题要求你在升序无重复元素的数组里查找目标值，找到返回下标，找不到返回-1。这是最纯粹的二分查找应用，没有重复元素，也就没有左右边界的纠结，非常适合作为第一道练手题。
用Python实现的左闭右闭版本如下：
class Solution: def search(self, nums: List[int], target: int) -> int: left, right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return -1这里有个Python特有的小细节：(left + right) // 2在left和right非常大时可能溢出（虽然Python整数没有真正溢出，但思想上要养成习惯）。更稳妥的写法是left + (right - left) // 2，这个写法在任何语言里都是安全的，也是面试官希望看到的。
4.2 PTA函数题的特点与应对
如果刷的是PTA平台，你可能会遇到一类"函数题"，比如题目要求你实现一个二分查找函数，函数原型形如：
int Search(int a[], int n, int x) { // 你的实现 }这类题的判题逻辑和LeetCode不太一样：它只测试你这个函数，不关心主函数怎么写。这就意味着你必须严格按照题目给定的函数签名来实现，返回值的语义也要看清——有的题找不到返回-1，有的题返回0或返回插入位置，每个题都不一样。
我之前在PTA上就栽过一次。那道题要求"若查找到，返回其下标；若未找到，返回其应该插入的位置"，我直接套了LeetCode的模板返回-1，结果一半测试点挂掉。所以在PTA做题，第一件事不是写代码，而是仔细读题：确认返回值语义、边界下标、是否处理重复元素。
4.3 刷这道题时的三个常见错误
我总结了三个初学阶段最高频的错误，几乎每个初学者都要踩一遍：
- 忘了数组为空：
nums.size() == 0的时候，right = -1，如果while条件写left <= right，第一轮就不会进入，返回-1，其实没问题。但如果你在循环外用了nums[mid]，就会越界崩溃。 - mid计算错误：直接写
(left + right) / 2，当left和right都接近int最大值时，两数之和可能溢出变成负数，mid直接算错。这个在LeetCode上不会遇到，但在系统设计或大数组场景下有实际风险。 - 返回了mid而不是下标：听起来很蠢，但确实有人在找到目标后忘记
return mid，而是在循环结束后return left或return -1，导致明明找到了，结果还是错的。
还有一个关于调试的经验：如果代码行为不正常，我建议你在每一轮while开始处打印left、mid、right三个值，观察它们的变化轨迹。只要区间在严格收缩，就说明逻辑是对的；如果发现某个值反复出现不变化，就说明边界更新出了问题。
5. 进阶：查找左边界和右边界
5.1 有重复元素时，问题一下子变复杂了
LeetCode 704是无重复元素的，代码随想录在后面安排了"有序数组查找第一个/最后一个目标值"的题目。当数组变成[1, 2, 3, 3, 3, 4, 5]，目标值是3，普通二分可能返回下标2或者4，但你不能确定是哪个。
这时候标准二分查找的return mid就不适用了。我们需要找"左边界"——第一个等于target的下标；以及"右边界"——最后一个等于target的下标。
先说查找左边界的思路：当你发现nums[mid] == target时，不急着返回，而是把right往左收缩，继续在左半边找。这样就保证了找到的一定是最左边的那个。
int findLeftBound(vector<int>& nums, int target) { int left = 0, right = nums.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else { // 大于等于target时，都收缩right right = mid - 1; } } // 循环结束时，left指向第一个不小于target的元素 if (left < nums.size() && nums[left] == target) return left; return -1; }注意这里的分支设计很巧妙：nums[mid] >= target时都走right = mid - 1，等于的情况也向左收缩；而nums[mid] < target时向右收缩。这样出口处left指向的位置就是左边界。
查找右边界正好是对称思路：当nums[mid] == target时，不急着返回，把left向右收缩。
int findRightBound(vector<int>& nums, int target) { int left = 0, right = nums.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] <= target) { left = mid + 1; // 等于的情况也向右收缩 } else { right = mid - 1; } } // 循环结束时，right指向最后一个不大于target的元素 if (right >= 0 && nums[right] == target) return right; return -1; }这两个函数理解了之后，你应该能直观感受到二分查找的核心思维——它不仅仅是"找到目标"，更是"找到某个条件下的临界位置"。左边界就是"第一个满足>= target的位置"，右边界就是"最后一个满足<= target的位置"。
5.2 重复元素场景下的真实应用
这种左右边界查找在工程中不是花架子，最常见的场景是：你要在一个有序的数据流中统计某个值的出现次数。朴素做法是找到任意一个位置后向左向右线性扩展，但如果有大量重复值，线性扩展最坏会退化到O(n)。
更稳的做法是：先用左边界查找找到起点，再用右边界查找找到终点，然后count = rightBound - leftBound + 1。这样整体仍然保持O(log n)的复杂度。我在实际处理日志时间戳统计时就遇到过这个需求，用二分定位到"最早出现该状态的时间点"和"最晚出现该状态的时间点"，然后一次切片搞定，完全不用遍历全部日志。
5.3 一个隐蔽的坑：mid取整方向与边界收缩方向不匹配
查右边界时，如果mid始终取的是下取整（也就是left + (right - left) / 2），并且收缩方式是left = mid，就会出问题。举例说明：
left = 3, right = 4，mid = 3；- 如果
nums[3] <= target，则left = mid = 3，left原地不动； - 下一轮
left = 3, right = 4，mid还是3，循环永远跳不出去。
解决办法有两个：一是当收缩策略是left = mid时，把mid的计算改成上取整：mid = left + (right - left + 1) / 2；二是仍然用下取整，但把收缩策略改成left = mid + 1。我在写查找右边界时，直接选择了第二种，代码更简单，也不容易犯错。这个细节，大概只有被死循环折磨过的人才会上心。
6. 二分思想的高阶应用与刷题建议
6.1 在值域上做二分：答案本身是分界点
二分查找的价值远不止于"在数组里找数字"。我是在刷LeetCode 875（爱吃香蕉的珂珂）时才彻底想通这一层的。题目要求在H小时内吃完所有香蕉，求最小的速度K。你可以直接猜一个K，然后验证在K速度下能不能按时吃完；如果K不够大，就加大；如果K够大，就减小——这不就是一个在[1, maxPile]值域上的二分吗？
核心代码逻辑长这样：
class Solution { public: int minEatingSpeed(vector<int>& piles, int h) { int left = 1, right = *max_element(piles.begin(), piles.end()); while (left < right) { int mid = left + (right - left) / 2; if (canFinish(piles, h, mid)) { right = mid; // mid可行，尝试更小的速度 } else { left = mid + 1; // mid不可行，必须更大的速度 } } return left; } bool canFinish(vector<int>& piles, int h, int speed) { int hours = 0; for (int pile : piles) { hours += (pile + speed - 1) / speed; } return hours <= h; } };这里的关键点在于：单调性体现在"速度K越大，所需时间越少"，所以canFinish是一个单调递减函数。判断条件成立时收缩右边界，不成立时收缩左边界，最终收敛到满足条件的最小值。这个模式在力扣上非常多：1011（在D天内送达包裹）、410（分割数组的最大值）、668（乘法表中第k小的数），全是同一个套路。
6.2 浮点数二分与整数二分的差异
浮点数二分和整数二分有个很大的不同：整数二分有明确的"边界"概念，循环靠while (left <= right)或while (left < right)控制；浮点数二分不存在"区间为空"的概念，它靠的是精度控制。比如计算平方根：
double sqrtByBinary(double x, double eps = 1e-8) { double left = 0, right = max(1.0, x); while (right - left > eps) { double mid = left + (right - left) / 2; if (mid * mid < x) { left = mid; } else { right = mid; } } return left; }注意浮点数二分里的边界更新是left = mid或right = mid，不用加减1，因为浮点数没有"相邻整数"的概念，严谨地保留mid即可。精度的选择也有讲究——1e-8通常够用，要求高时用1e-10，但太小会导致循环次数过多，性能下降。
6.3 刷题路线上的一点建议
如果你是从零开始刷算法题，我建议的顺序是这样的：
- 先把704这道题用两种写法各写一遍，写到不需要思考就能写对的程度；
- 再刷35（搜索插入位置）、34（在排序数组中查找元素的第一个和最后一个位置），感受边界变种的差异；
- 之后做875、1011这类"答案二分"的题目，把思维从"数组"扩展到"值域"；
- 最后可以挑战一下4（寻找两个正序数组的中位数），这道题把二分用到了极致，难度直接上一个台阶，刷不过也不用气馁。
二分查找的高阶应用远不止这些。后来我在读STL源码时发现，lower_bound和upper_bound这两个常用函数，内部就是基于类似的二分逻辑实现的。理解了左右边界查找，你其实就把lower_bound和upper_bound的源代码读懂了。
刷题和平时写业务代码是两种思维。业务代码讲究的是"跑通就好"，算法题讲究的是"边界也要稳"。二分查找就是训练这种边界感最好的入门题——它足够简单，让你能把注意力完全集中在循环不变量的维护上；它又足够深刻，哪怕已经工作多年，我偶尔写一些复杂的二分变种还是会先停下来确认一下区间的开闭性。
如果说有什么最后的建议，那就是：不要背模板，要背逻辑。当你看到任何一个二分题目，先在脑子里回答三个问题——搜索区间是什么？循环终止后left和right各自指向什么位置？区间定义决定了哪些边界更新必须偏移？这三个问题想清楚了，代码怎么写都是对的。
