很多初学算法的朋友应该都有过这种体验二分查找看代码的时候觉得逻辑清清楚楚不就是每次砍一半嘛可真到了自己动手写不是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(vectorint nums, int target) { int left 0; int right nums.size() - 1; // 关键1right 指向最后一个有效元素 while (left right) { // 关键2left right 时区间内还有一个元素需要判断 int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid 1; // 关键3mid已经比较过了排除它区间变成 [mid1, right] } else { right mid - 1; // 关键3排除mid区间变成 [left, mid-1] } } return -1; }三个关键点的逻辑是一致的因为区间包含right所以当left right时不能退出循环还要判断这个元素。又因为mid已经被比较过所以无论走哪个分支都不能让新区间再包含mid必须1或-1偏移掉。2.3 版本二左闭右开写法左闭右开意味着right指向的元素不参与候选它只是一个上界标记。int binarySearch(vectorint nums, int target) { int left 0; int right nums.size(); // 关键1right 指向最后一个元素的下一个位置 while (left right) { // 关键2left right 时区间为空循环终止 int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid 1; // 关键3mid已排除新区间为 [mid1, right) } else { right mid; // 关键3mid已排除但新区间要包含左边界所以 right mid } } return -1; }注意这里最反直觉的一点当nums[mid] target时更新的是right mid而不是right mid - 1。因为在左闭右开定义下right本身就不在候选区间里把right挪到mid的位置等于把mid和它右边的所有元素都排除了而[left, mid)这个新区间依然完整且合法。2.4 两种版本的实际对比我整理了一个对比表格方便你快速对照记忆对比维度左闭右闭 [left, right]左闭右开 [left, right)初始rightnums.size() - 1nums.size()循环条件left rightleft right收缩左边界left mid 1left mid 1收缩右边界right mid - 1right mid空区间判断left rightleft 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 2nums[2] 5命中返回2。这个例子太顺了看不出边界处理的必要。换一个更刺激的场景查找target 6数组中不存在。继续用左闭右闭初始化left 0, right 4第一轮mid 2nums[2] 5 6所以left mid 1 3。此时区间[3, 4]第二轮mid 3 (4-3)/2 3nums[3] 7 6所以right mid - 1 2。此时区间[3, 2]循环条件判断left right即3 2为false退出循环返回-1。注意第二轮结束后left right说明这个区间已经空了——所有可能的元素都被排除干净确实找不到6。这逻辑是严丝合缝的。再看左闭右开版本在同样场景下的表现初始化left 0, right 5第一轮mid 2nums[2] 5 6所以left 3区间[3, 5)第二轮mid 3 (5-3)/2 4nums[4] 9 6所以right mid 4区间[3, 4)第三轮mid 3 (4-3)/2 3nums[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(vectorint 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(vectorint 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 4mid 3如果nums[3] target则left mid 3left原地不动下一轮left 3, right 4mid还是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(vectorint 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(vectorint 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各自指向什么位置区间定义决定了哪些边界更新必须偏移这三个问题想清楚了代码怎么写都是对的。
很多初学算法的朋友应该都有过这种体验二分查找看代码的时候觉得逻辑清清楚楚不就是每次砍一半嘛可真到了自己动手写不是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(vectorint nums, int target) { int left 0; int right nums.size() - 1; // 关键1right 指向最后一个有效元素 while (left right) { // 关键2left right 时区间内还有一个元素需要判断 int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid 1; // 关键3mid已经比较过了排除它区间变成 [mid1, right] } else { right mid - 1; // 关键3排除mid区间变成 [left, mid-1] } } return -1; }三个关键点的逻辑是一致的因为区间包含right所以当left right时不能退出循环还要判断这个元素。又因为mid已经被比较过所以无论走哪个分支都不能让新区间再包含mid必须1或-1偏移掉。2.3 版本二左闭右开写法左闭右开意味着right指向的元素不参与候选它只是一个上界标记。int binarySearch(vectorint nums, int target) { int left 0; int right nums.size(); // 关键1right 指向最后一个元素的下一个位置 while (left right) { // 关键2left right 时区间为空循环终止 int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid 1; // 关键3mid已排除新区间为 [mid1, right) } else { right mid; // 关键3mid已排除但新区间要包含左边界所以 right mid } } return -1; }注意这里最反直觉的一点当nums[mid] target时更新的是right mid而不是right mid - 1。因为在左闭右开定义下right本身就不在候选区间里把right挪到mid的位置等于把mid和它右边的所有元素都排除了而[left, mid)这个新区间依然完整且合法。2.4 两种版本的实际对比我整理了一个对比表格方便你快速对照记忆对比维度左闭右闭 [left, right]左闭右开 [left, right)初始rightnums.size() - 1nums.size()循环条件left rightleft right收缩左边界left mid 1left mid 1收缩右边界right mid - 1right mid空区间判断left rightleft 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 2nums[2] 5命中返回2。这个例子太顺了看不出边界处理的必要。换一个更刺激的场景查找target 6数组中不存在。继续用左闭右闭初始化left 0, right 4第一轮mid 2nums[2] 5 6所以left mid 1 3。此时区间[3, 4]第二轮mid 3 (4-3)/2 3nums[3] 7 6所以right mid - 1 2。此时区间[3, 2]循环条件判断left right即3 2为false退出循环返回-1。注意第二轮结束后left right说明这个区间已经空了——所有可能的元素都被排除干净确实找不到6。这逻辑是严丝合缝的。再看左闭右开版本在同样场景下的表现初始化left 0, right 5第一轮mid 2nums[2] 5 6所以left 3区间[3, 5)第二轮mid 3 (5-3)/2 4nums[4] 9 6所以right mid 4区间[3, 4)第三轮mid 3 (4-3)/2 3nums[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(vectorint 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(vectorint 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 4mid 3如果nums[3] target则left mid 3left原地不动下一轮left 3, right 4mid还是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(vectorint 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(vectorint 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各自指向什么位置区间定义决定了哪些边界更新必须偏移这三个问题想清楚了代码怎么写都是对的。
