1. 二分查找为什么总是看着简单一写就挂刷过LeetCode的朋友大多有过这种尴尬翻开题解觉得二分查找就那几行思路清清楚楚可一旦自己在编辑器里动手不是死循环就是返回错位置左调右调十分钟最后默默点开题解——发现只是while条件里少了个等号或者mid的更新写反了。我当年刷Hot 100里的二分题时就有强烈体会二分查找不是背模板的算法它是对区间不变量理解程度的试金石。热词里那些二分查找pta函数、hot100题的搜索记录背后大概率都是同一个场景算法考试或面试手撕代码时在边界条件上卡壳。先说结论Hot 100里真正涉及二分查找的题目大概六七道它们表面各不相同有的在旋转数组里找目标值有的在二维矩阵里定位元素有的找峰值有的求平方根——但底层全部可以收敛到同一个思维框架。这篇文章就把这些题目放在一起拆解看完你会理解为什么说二分查找的核心不是折半这个动作而是每一步都在维护一个答案一定存在于当前区间内的保证。适合谁来读两类人。第一类是刚刷完基础题、准备攻克Hot 100的求职者需要理清二分的各种变形第二类是已经能AC简单二分题但遇到边界变体就容易翻车的同学。我会把[left, right]区间、left right和left right两种写法的本质区别讲透再逐题拆解Hot 100里的二分题最后给出工程场景下的调试方法和个人经验。2. 边界条件才是二分查找的真身先搞清楚你在维护什么2.1 两种共识式写法背后的分歧网上关于二分的模板少说有十几种最常见的两类是# 写法A左闭右闭 l, r 0, len(nums) - 1 while l r: mid (l r) // 2 if nums[mid] target: return mid elif nums[mid] target: l mid 1 else: r mid - 1 return -1# 写法B左闭右开 l, r 0, len(nums) while l r: mid l (r - l) // 2 if nums[mid] target: l mid 1 else: r mid return l很多初学者两种都背却不知道为什么有时候用left mid 1有时候用left mid。实际上每一种写法都对应一个区间语义约定。写法A的语义是[left, right]内的元素都尚未被排除mid如果小于target目标值只可能在mid右边所以left mid 1如果mid大于target目标只可能在mid左边所以right mid - 1。循环结束条件是left right说明整个区间已经被排空了目标不存在。写法B的语义是[left, right)区间内可能存在目标值mid小于target时移动leftmid不小于target时把right收敛到mid。循环结束时left right而这个位置就是第一个不小于target的下标。哪种更好我的经验是写算法题用写法A更直观因为判断等于的情况可以提前返回写二分边界查找类问题找第一个大于等于target的位置用写法B更安全因为它天然能处理重复元素。关键是不要混用——一会儿维护[l, r]一会儿心里想的是[l, r)那必然翻车。2.2 一个必须刻在脑子里的细节mid的计算mid (l r) // 2和mid l (r - l) // 2在数学上完全等价但在实际编程中却可能有天壤之别。C和Java里l r可能整数溢出Python虽然没有这个问题但为了习惯统一我建议一律写成l (r - l) // 2。这个习惯在写x的平方根这种数值二分时尤其重要——因为r可能非常大l r在某些语言里直接溢出变成负数整个二分直接报废。还有一个很多人没注意的细节当区间收缩到只剩两个元素时mid取左中位还是右中位决定了死循环是否发生。如果条件是while l r且r mid这种更新方式那么mid (l r) // 2左中位是安全的如果条件是while l r且l mid那么必须取右中位mid (l r 1) // 2否则当l和r相邻时mid永远等于l区间不再缩小死循环。这个坑我在写寻找旋转排序数组中的最小值时踩过。那道题的标准解法里有r mid如果mid取右中位某个时刻区间会卡住不动程序超时。后来我总结了一条铁律只要r midmid就取左中位只要l midmid就取右中位。不需要背推导一下就能想通区间缩小到[0, 1]时如果mid等于左端点且l mid下次循环区间还是[0, 1]直接死循环。3. Hot 100二分题的全景拆解同一套内核六种包装Hot 100里的二分题其实是很好的变形训练因为它们虽然都用二分但考察的侧重点完全不同。我把常见的几道整理成一张表方便你先建立整体认知题目二分类型核心考点易错点搜索旋转排序数组旋转数组中找目标值判断哪半段有序相等元素导致的判断分支错误在排序数组中查找元素的第一个和最后一个位置左右边界二分两次二分分别找上界和下界在找到目标值后直接返回导致边界丢失寻找旋转排序数组中的最小值旋转数组求极值与右端点比较mid取左中位还是右中位搜索二维矩阵一维索引映射到二维mid // n和mid % n坐标换算忘记n是列数而非行数寻找峰值局部极值二分的派生与相邻元素比较后收缩区间忽略峰值定义要求左右严格小于x的平方根数值型二分乘法溢出与精度控制返回right还是left边界是0和1这六道题如果按考察逻辑分其实是三类标准有序数组查找如搜索二维矩阵本质是一维有序数组、旋转数组的循环有序处理搜索旋转数组、找最小值、极值收敛问题寻找峰值、x的平方根。下面我按这三类逐一说清楚。3.1 标准有序数组查找搜索二维矩阵的坐标陷阱搜索二维矩阵算Hot 100二分题里最友好的一道。每行从左到右递增且下一行的第一个元素大于上一行的最后一个元素这保证了整个矩阵可以展开成一个有序一维数组。既然是有序数组直接上标准二分即可。关键点是坐标映射。假设矩阵是matrix[m][n]m行n列你把一维索引mid映射回二维坐标时行号是mid // n列号是mid % n。这里n是列数不是行数很多人写反了。我见过不止一个人在这里用mid // m去算行号结果矩阵不是方阵就全乱套。def searchMatrix(self, matrix: List[List[int]], target: int) - bool: m, n len(matrix), len(matrix[0]) l, r 0, m * n - 1 while l r: mid l (r - l) // 2 val matrix[mid // n][mid % n] if val target: return True elif val target: l mid 1 else: r mid - 1 return False这道题还有一个进阶版本矩阵行内递增、行首元素不一定比上一行末尾大那就不能用一维展开得先对行做二分找所在行再对行内做二分。Hot 100暂时没把这个进阶版本作为独立题但面试官经常追问建议你也写一遍——实际上是同一个二分套两层。3.2 旋转数组二分查找最经典的模式变形旋转数组是排序数组在某个位置被断开后拼接而成比如[4,5,6,7,0,1,2]。这种数组整体不是有序的但有一个关键性质从mid切开后左半段和右半段至少有一段是严格有序的。这正是二分能继续应用的前提。在搜索旋转排序数组里核心逻辑是计算mid比较nums[mid]和nums[l]。如果nums[l] nums[mid]说明左半段有序否则右半段有序。确定target落在哪半段。如果左半段有序且nums[l] target nums[mid]target在左半段r mid - 1否则l mid 1。右半段类比。这里有个判断顺序的讲究先判断哪半段有序再判断target是否在该半段内。如果你先比较target和nums[mid]再尝试定位很容易漏掉target可能在有序段之外的情况。def search(self, nums: List[int], target: int) - int: l, r 0, len(nums) - 1 while l r: mid l (r - l) // 2 if nums[mid] target: return mid if nums[l] nums[mid]: # 左半段有序 if nums[l] target nums[mid]: r mid - 1 else: l mid 1 else: # 右半段有序 if nums[mid] target nums[r]: l mid 1 else: r mid - 1 return -1寻找旋转排序数组中的最小值则换了个思路不找目标值找极值。此时比较对象应该是nums[mid]和nums[r]而不是nums[l]。原理是如果nums[mid] nums[r]说明最小值在右半段因为左半段是旋转后的前缀转折点一定在右侧反之最小值在左半段或就是mid对应位置。这里注意mid取左中位且循环条件用l r更新时r mid不是mid - 1因为nums[mid]本身可能正是最小值不能把它排除掉。如果你取右中位同一条件下l和r相邻时永远不会更新死循环唤醒PTA评测时的超时提示。至于存在重复元素的旋转数组这类题目不在Hot 100里但面试常作为延伸。核心变化是当nums[l] nums[mid] nums[r]时无法判断哪边有序只能把l和r各收缩一位最坏情况退化成O(n)。这个退化的原因在面试时能讲清楚基本就能过关。3.3 极值收敛型二分寻找峰值和x的平方根寻找峰值严格来说不完全像二分但它通过逐渐向峰值方向收缩区间的方式把问题收敛到O(log n)是二分思维在极值问题上的体现。题目定义峰值是nums[i] nums[i-1]且nums[i] nums[i1]的元素数组任意相邻元素不相等且nums[-1] nums[n] -无穷。关键思路比较nums[mid]和nums[mid 1]。如果nums[mid] nums[mid 1]说明mid处于上坡路段峰值一定在右侧否则峰值在左侧包括mid本身。这个思路不需要考虑全局单调性直接收缩即可。def findPeakElement(self, nums: List[int]) - int: l, r 0, len(nums) - 1 while l r: mid l (r - l) // 2 if nums[mid] nums[mid 1]: l mid 1 else: r mid return l你可能会问这个比较为什么不用nums[mid - 1]因为mid 0时mid - 1越界很多人的bug就出在这里。比较中点和它右侧邻居天然避开了左边界越界问题。x的平方根则是经典数值二分。要找sqrt(8)的整数部分直接在[0, x]区间上二分判断mid * mid是否大于x。两个坑需要注意一是mid * mid在C/Java里可能溢出要用mid x / mid这种除法形式代替乘法二是边界条件循环结束时返回right而不是left因为我们要的是平方小于等于x的最大整数left会停在第一个平方大于x的位置。def mySqrt(self, x: int) - int: if x 2: return x l, r 0, x while l r: mid l (r - l) // 2 if mid x // mid: r mid - 1 else: l mid 1 return r顺便说一句业界实际求平方根会用牛顿迭代法收敛更快但面试手撕时写二分就好——它更能体现你对答案可枚举区间单调判定这个框架的理解。4. 最绕的一道查找元素的第一个和最后一个位置这道题我认为是Hot 100二分题里最值得反复手写的因为它把边界查找这一二分的高级主题讲透了。题目给一个有重复元素的升序数组比如[5,7,7,8,8,10]要求找到target比如8第一次和最后一次出现的下标找不到返回[-1,-1]。很多人的第一反应是先用普通二分找到任意一个等于target的下标然后向左向右线性扫描。这个思路在极端情况下会退化到O(n)——如果整个数组全是target二分找到中位后就变成了线性遍历。显然Hot 100不会饶过这个解法面试官也会追问能不能保持O(log n)。正确做法是做两次二分分别查找左边界和右边界。左边界定义为第一个 target的位置右边界定义为第一个 target的位置结果就是[左边界, 右边界 - 1]。这样写的好处是两个辅助函数都只依赖于数组有序这一个性质不容易出错。def searchRange(self, nums: List[int], target: int) - List[int]: def lower_bound(t): l, r 0, len(nums) while l r: mid l (r - l) // 2 if nums[mid] t: r mid else: l mid 1 return l left lower_bound(target) right lower_bound(target 1) - 1 if left len(nums) and nums[left] target: return [left, right] return [-1, -1]注意这里的细节右边界找的是target 1即第一个大于target的位置然后减1。如果target是数组最大值target 1不会存在但lower_bound返回的是len(nums)减1后可能越界所以判断时要加left len(nums)防止越界访问。很多人不理解为什么要用[mid] t而不是[mid] t。我这么解释你就明白了我们要找的是第一个大于等于t的位置所以mid位置如果已经大于等于t说明答案在左侧或就是mid所以r mid如果mid位置小于t说明答案在右侧所以l mid 1。这里隐含了while l r循环结束时l r的性质它收敛到第一个满足条件的位置。相同的辅助函数思路可以直接平移到搜索插入位置Hot 100里有的那题要求返回target应该插入的下标其实就是lower_bound(target)。你会发现一套二分边界查找的板子可以刷三道题这就是理解边界语义带来的杠杆效应。5. 刷LeetCode之外的二分工程与考试中的真实应用有人会问二分查找在工程里到底用不用总不能天天刷题吧。真用只是你不一定感知得到。我记得有段时间在做日志检索系统的区间查询需求是找到某时间戳之后的第一条日志。日志文件按时间递增排列几十万条日志如果for循环逐条匹配平均延迟好几毫秒当时直接用了二分查找定位起始偏移量单次查询降到微秒级。当时我就在想这不就是在排序数组中查找元素的第一个和最后一个位置的下界查找吗其他常见场景包括git bisect的命令行工具。它内部就是在提交历史里二分查找第一个引入bug的commit原理和寻找峰值如出一辙——判断当前commit的测试结果然后向左或向右收缩区间。数据库索引的B树查找。B树每层节点的键值是有序的节点内部的键值查找用的就是二分。在线判题系统PTA、LeetCode等的浮点数二分。比如要求sqrt(x)保留n位小数就需要在[0, x]区间上不断二分直到区间长度小于精度阈值。这个写法和整数二分的区别在于循环条件不再是比较索引大小而是比较r - l eps。如果你在准备考试或者刷PTA函数题我强烈建议你把二分模板理解到不问为什么也能写对的程度。考场上可没有时间让你慢慢推导mid取左中位还是右中位。我的个人做法是把循环不变量四字默念一遍——每次循环开始时答案一定在当前的[l, r]区间内每一次更新区间时都要保证这个性质不丢失。只要区间不变量成立循环结束的位置一定就是答案。举例来说在在排序数组中查找第一个和最后一个位置里我用lower_bound函数时心里默认的区间语义是[l, r)所以我理直气壮地用r len(nums)初始化nums[mid] t时r mid保证答案要么在mid处要么在mid左侧而mid本身不会被错误排除。这套心理模型清晰了边界就不会错。6. 我的调试三板斧与踩坑实录最后分享一点排错经验。二分写挂了不要反复盯着代码目验大概率看不出问题。按下面的流程走一遍打印关键状态。在循环里加一行print(l, r, mid, nums[mid])跑一个小用例[1,2,3,4,5]观察区间收敛趋势。如果你看到mid反复等于l几乎可以断定是中位偏向问题。用最小反例测试。准备三个用例空数组、长度1的数组、重复元素的数组。这三个用例能暴露绝大多数边界问题。比如平方根题目如果x 0或x 1不过多半是边界条件提前返回没写好如果重复元素数组的首次/末次位置返回错误多半是等号方向搞反了。不要混用区间语义。这是我最想强调的。你一旦选了[l, r]初始化r len(nums) - 1循环条件l r那所有更新都按闭区间来你一旦选了[l, r)就初始化r len(nums)循环l r更新时严格遵守r mid而不是r mid - 1。左右横跳的人十个有九个会写出死循环或漏掉答案。我自己踩过比较深的一个坑是寻找旋转排序数组中的最小值里用nums[l]和nums[mid]比较。当时想着找最小值嘛应该和左边界比结果在数组完全递增旋转点在第0位时翻车了。因为nums[l] nums[mid]的时候你眼前左半段有序但无法判断转折点是否在右半段和左边界比较得到的信息不足以区分整体有序和前一段有序但最小值在后一段两种情况。换成和右边界nums[r]比较信息量一下子就够用了。这类经验如果只看题解是学不到的只有自己跑一遍错的案例才能把为什么和右边界比刻进记忆里。7. 说点自己的体会Hot 100的二分题全部吃透之后你会发现自己再看二分相关的新题第一反应从背模板变成了先判断区间不变量是什么再设计收缩条件。这个转变才是刷这组题真正的收益。我个人的建议是刷二分专题时不要追求刷题数量而是把每道题的边界条件变体都推演一遍。比如同一道搜索旋转排序数组你可以自己追问如果数组里有重复元素怎么办如果要返回旋转点下标怎么办如果要找右边界怎么办这些追问会让你在考场和面试中从容很多。再分享一个小技巧二分题的单元测试写起来特别快你完全可以平时就用一个简单的脚本把所有边界用例自动化跑一遍包括空数组、单元素数组、目标值在首尾、目标值不存在、重复元素、极大数值等。花十分钟建立自己的二分回归用例集之后每次遇到新的二分题都能快速验证模板非常划算。