1. 为什么一道二分查找值得单独写一篇做了九天算法打卡前八天都在跟数组的基本遍历、插入、删除打交道到了第四天正式开始接触第一种真正意义上的查找算法。704这道题题面一句话就能看完给定一个升序整数数组和一个目标值返回目标值在数组中的下标不存在就返回 -1。看起来简单但二分查找恰恰是那种“一看就会、一写就错”的典型。网上关于这道题的讨论常年不断核心分歧就集中在两点循环条件到底用left right还是left right更新边界时mid到底要不要加一减一。这两个问题不搞清楚代码就是改来改去碰运气。这道题适合谁来学两种人。第一种是刚接触算法题的新手需要从这道题建立起“边界意识”——写任何算法题边界条件往往是正确性的关键第二种是已经刷过一阵但总是卡在二分变体题的人比如在旋转数组里找最小值、在有序矩阵里找目标值这些进阶题追根溯源底层都是 704 题的区间控制逻辑。把这道题吃透后面很多看似复杂的题都会豁然开朗。我在实际刷题时最大的感受是二分查找考的不是“懂不懂原理”而是“能不能把区间的定义贯彻到底”。很多人写错不是不知道二分的思想而是写代码的过程中区间的含义悄悄变了。所以这篇文章我会从原理开始讲起重点放在两种主流写法上最后附上我自己的调试记录和常见坑点尽量让你一次性把这道题写稳。2. 二分查找的前提条件与核心思想2.1 有序数组为什么是硬性要求二分查找的第一个前提是数据必须存储在数组中也就是支持通过下标随机访问第二个前提是数组本身具备单调性通常是升序。这两个前提缺一个都不行。先说说“有序”。二分查找的每一步都在做一件事拿中间元素跟目标值比然后砍掉一半不可能的区域。这个过程能成立依赖于一个关键逻辑——如果目标值比中间元素大那么目标值一定在右半边如果目标值比中间元素小那么目标值一定在左半边。这个“一定”从哪里来就是从数组的有序性来的。只有数组有序你才能确信中间元素左侧的所有元素都不大于它右侧的所有元素都不小于它。假如数组是无序的中间元素比目标值小目标值完全可能出现在左半边因为你根本不知道左边有哪些数砍掉左半边就会漏掉答案。很多人初学时会忽略一个细节这里说的有序默认是升序。但实际工作中遇到的数组也可能是降序的比如按时间倒序排列的日志列表。降序数组同样可以用二分查找只是判断逻辑要反过来——中间元素比目标值小那答案在左边中间元素比目标值大答案在右边。我建议在学习阶段就把升序和降序的写法都练一遍因为这能帮你摆脱“背模板”的坏习惯真正理解每一步判断的依据。再来说说“随机访问”。“随机”这个词在这里不是“随机数”的意思而是指可以不依赖顺序、直接跳到任意位置访问元素。数组在内存里是一段连续空间知道下标就能直接算出内存地址访问时间恒定为 O(1)。但链表就不行链表虽然也是线性结构可它每个节点只知道自己下一个邻居的位置想拿到第 n 个节点必须从头一个个走过去时间复杂度是 O(n)。如果数据结构是链表二分查找每次取中间元素都要遍历整个链表一次 O(n)二分 O(logn) 次总复杂度退化到 O(nlogn)比直接一遍线性查找还慢。这也是为什么二分查找几乎总是跟“数组”绑定出现。2.2 折半搜索的本质每次排除一半二分查找的时间复杂度是 O(logn)这在算法题里是一个非常诱人的数字。直观感受一下一个长度为 100 万的升序数组线性查找最坏需要比较 100 万次而二分查找最多比较 20 次左右因为 2 的 20 次方正好超过 100 万。数据规模每翻一倍二分查找只多一次比较这种增长曲线在数据量大的时候优势极其明显。每次比较能排除一半区域这个逻辑可以用一个生活化的例子理解。比如你在看一本 1000 页的书知道里面某一页有个词但你不知道页码。你不会从第 1 页开始逐页翻而是先翻到中间第 500 页看看这个词是在左边还是右边如果判断在左边就翻到第 250 页继续找。每一步都把搜索范围缩小一半最多翻十次左右就能找到。二分查找在数组上做的事完全一样。但我必须提醒一点二分查找的 O(logn) 只体现在“比较的次数”上。实际工程里数组的访问速度和比较操作的常数因子也很重要。在小规模数据下比如数组长度只有几十二分查找和线性查找的耗时差距几乎感觉不到甚至还可能因为分支判断更多而略慢。所以工程上不要无脑二分通常数组规模在几百以下时线性查找的可读性和简洁性更值得优先考虑。算法题的训练价值在于建立复杂度思维但落地到项目里还要结合真实数据规模做权衡。2.3 循环不变量的概念整个算法的灵魂二分查找最抽象也最关键的概念是“循环不变量”。这个词听起来吓人但理解起来并不难它指的是在循环执行的每一步某个条件始终成立。对于二分查找这个不变量就是——你定义的搜索区间里一定包含可能的目标值位置。换句话说你在写代码之前要明确一个具体规则我维护的这个[left, right]区间代表的是“目标值可能存在的位置”。每次循环结束收缩区间时都必须保证新的[left, right]依然满足这个语义。很多人写错就是因为收缩区间时把可能包含答案的位置排除掉了或者把已经排除掉的位置又重新包含进来导致循环不变量被破坏。举个例子如果你定义的是左闭右闭区间也就是left和right都包含在搜索范围内那么当你判断nums[mid] target时说明mid这个位置以及它左边的所有位置都不可能存在目标值下一步应该把left更新为mid 1。但如果此时你把left更新成mid那么mid这个已经确认不等于目标值的位置又回到了搜索区间里虽然这次不会出错但会破坏不变量最终可能导致死循环。所以写二分查找之前先在纸上写下这句话“我维护的区间范围到底包含哪些位置”把这个定义写清楚再动手写代码边界条件就会变得水到渠成。这不是玄学而是很多高级程序员在代码评审时一定会追问的问题。3. 704 题完整解题两种区间写法的细节对比3.1 题目原文与关键约定题目给的是一个升序整数数组nums和一个整数target要求在数组中找到target的下标如果不存在则返回 -1。题目还明确说数组中的元素是唯一的这个条件很重要它意味着不存在“重复元素该返回哪一个下标”的歧义。前置条件是这样的项目说明输入升序整数数组 nums、目标值 target输出target 的下标不存在时返回 -1条件数组中无重复元素示例nums [-1,0,3,5,9,12]target 9输出 4边界nums 长度可为 0target 可能小于最小元素或大于最大元素在动手写代码前先想清楚几个边界场景数组长度为零的情况、目标值比所有元素都小、目标值比所有元素都大、目标值刚好在数组最左侧或最右侧。这四个场景在代码里都必须能正确结束循环并返回 -1 或正确下标。3.2 左闭右闭写法最直观、最好理解第一种写法也是最推荐新手掌握的写法是左闭右闭区间。所谓“左闭右闭”就是left指向搜索区间的第一个位置right指向搜索区间的最后一个位置区间写作[left, right]。这意味着left和right指向的位置本身也在搜索范围内。代码如下使用 Pythondef search(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid - 1 return -1为什么循环条件是left right因为当left right时[left, right]区间里还剩一个元素这个元素还没有被比较过它仍然可能是目标值。所以只要left right循环就必须继续。如果你写成left right那么当左右指针相遇时会直接跳出循环最后一个元素没有检查答案就被漏掉了。为什么nums[mid] target时要把left更新成mid 1因为mid这个位置的元素已经确认小于目标它自己肯定不是答案同时有序性决定了它左边的元素也都小于它更不可能等于目标值。所以可以安全地把左边界收缩到mid 1把mid及左侧全部排出去。对称地nums[mid] target时right mid - 1也是同理。这种写法我在讲解时最喜欢用因为它和人的直觉一致区间有明确的头尾挨个排除就好。只要保持“区间内每个元素都还没被比较过”这个心态边界条件就不会写错。3.3 左闭右开写法工程中更常见的风格第二种写法是左闭右开区间区间写作[left, right)。注意right指向的不是搜索区间的最后一个元素而是“最后一个元素的下一个位置”。搜索区间实际包含的是left到right - 1这些位置。def search(nums, target): left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid return -1这种写法和左闭右闭有两个关键区别。第一个区别是初始值right初始为len(nums)而不是len(nums) - 1因为right本身不包含在搜索区间内所以它可以等于数组长度。这样写还有一个好处如果数组为空right初始为 0left也是 0left right不成立循环直接跳过返回 -1不用单独处理空数组。第二个区别是循环条件写成left right。为什么这里不用因为当left right时区间[left, right)是空的已经没有元素可以搜索了。空区间意味着搜索结束所以循环条件严格小于即可。如果写成当左右相等时还会再进入一次循环此时 mid 等于 left 也等于 rightmid 不在区间内访问nums[mid]可能越界这是初学者容易踩的坑。第三个区别是收缩边界的方式当nums[mid] target时right mid而不是mid - 1。原因是区间右端是开区间right不参与搜索把right设为mid就把mid及右侧全部排除了——mid已经不等于目标值它不该留在区间里而右开区间本来就不包含right指向的位置所以mid被自然排除。如果写成right mid - 1那mid - 1也会被排除而mid - 1这个位置还没被比较过可能包含目标值就被错误地丢掉了。两种写法各有拥护者。我的个人建议是左闭右闭适合学习和面试时讲解逻辑直观、不容易丢答案左闭右开在 C 的 STL 标准库和很多工程代码里更常见因为迭代器的end()普遍是开区间。但无论你用哪种最重要的是把区间定义写清楚不要混用。很多人写着写着就把两种写法的细节混在一起比如用左闭右闭的初始值搭配左闭右开的循环条件结果各种莫名其妙的问题。3.4 两种写法的对比与选择建议对比项左闭右闭 [left, right]左闭右开 [left, right)初始值left 0, right len(nums) - 1left 0, right len(nums)循环条件left rightleft right区间为空的条件left rightleft rightmid 偏大时更新right mid - 1right midmid 偏小时更新left mid 1left mid 1空数组处理需要特判 left right循环自动跳过推荐场景面试、初学工程代码、C 迭代器风格我在实战中遇到过很多次面试者两种写法来回切换的情况。面试官问“为什么循环条件是小于等于”回答“因为要保证区间不为空”这种答案没问题。但再问一句“你的区间是左闭右闭还是左闭右开”很多人就开始含糊了。这恰恰说明很多人的二分查找是背下来的而不是理解下来的。想真正掌握建议你分别用两种写法各写一遍然后用同样的测试用例跑一遍感受一下边界收缩的差异这套功夫值得花。4. 实操过程从读题到 AC 的完整记录4.1 测试用例的设计思路写代码前先设计测试用例这是一个被很多人忽略的好习惯。不要一上来就提交而是先在本地把下面这些场景过一遍。这是我刷 704 题时实际用的一组测试用例测试场景numstarget期望结果说明目标在中间[1,2,3,4,5]32常规场景目标在最左[1,2,3,4,5]10左边界目标在最右[1,2,3,4,5]54右边界目标不存在偏小[1,2,3,4,5]0-1小于所有元素目标不存在偏大[1,2,3,4,5]6-1大于所有元素目标不存在在中间[1,2,3,4,5]7-1落在数值区间内但不存在的数空数组[]1-1边界场景单元素命中[1]10单元素成功单元素未命中[1]2-1单元素失败两个元素[1,2]21最小规模的多元素场景这组用例覆盖了二分查找的几乎所有边界。我强烈建议你在本地把这组用例跑通后再提交。很多时候你以为自己代码写对了一提交发现超时或者报错问题往往不是“二分查找不会”而是某个边界场景没有覆盖到。4.2 逐行推演一遍循环过程以左闭右闭写法为例手动推演一个完整过程。数组 nums [-1,0,3,5,9,12]target 9。初始状态left 0right 5搜索区间 [0,5]包含全部 6 个元素。第一次循环mid 0 (5 - 0) // 2 2nums[2] 3。3 9说明目标值在右侧把 left 更新为 3。此时区间变为 [3,5]包含位置 3、4、5。第二次循环mid 3 (5 - 3) // 2 4nums[4] 9。9 等于目标值直接返回 4。整个过程只比较了两次。如果 target 9 而数组长度变成 100 万也只需要约 20 次比较这就是二进制对数的威力。再看一个目标不存在的情况。target 7同样的数组。第一次循环mid 2nums[2] 33 7left 3。第二次循环mid 4nums[4] 99 7right 3。此时 left 3right 3区间 [3,3] 不为空继续循环。第三次循环mid 3nums[3] 55 7left 4。此时 left 4right 3区间为空循环条件left right不成立跳出循环返回 -1。注意一个细节在这种写法下循环结束后 left 和 right 的关系有两种可能要么 left right 1要么 left 指向第一个大于 target 的位置。这为二分查找的变体题提供了伏笔比如寻找插入位置时循环结束后的 left 往往就是答案。现在不需要深究但可以留个心眼。4.3 常见错误与排查技巧实录我总结了自己踩过的坑也看过不少初学者犯的错集中排在前几位的是下面这些。第一个坑循环条件写错导致死循环或漏解。最常见的是左闭右闭写法里用了left right结果当数组长度为 1 且目标值就是那唯一一个元素时left 和 right 初始都为 0循环条件不满足直接返回 -1。排查方法很简单在纸上画出区间收缩过程每次都问自己“当前区间还剩哪些位置没查过”如果 left right 但那个位置还没查过那循环条件就有问题。第二个坑mid 计算溢出。早期教科书会写mid (left right) // 2。这个写法在 left 和 right 都很小的时候没问题但当数组长度接近编程语言中整型最大值的一半时left right可能溢出导致 mid 变成负数或错误的大数。工程上标准写法是mid left (right - left) // 2先算差值再除以二从根源上避免溢出。虽然刷题时数组长度很少那么大但养成这个习惯没有坏处而且这个写法在变体题里一样适用。第三个坑收缩区间时把答案排除了。这个坑特别隐蔽。左闭右开写法中当nums[mid] target时有人写成right mid - 1导致mid - 1这个还没比较过的位置被排除。如果正确答案恰好就在mid - 1结果就错了。排查这类问题的方法是每次收缩后在草稿纸上重新画一遍区间确认区间里包含的所有位置都还没有被排除。第四个坑忘记处理空数组。左闭右闭写法中right len(nums) - 1如果数组为空right 初始为 -1循环条件left right也就是0 -1不成立不会进入循环其实也能返回 -1。但如果你在循环前就访问了nums[0]或者对 right 做了其他操作就会有越界风险。左闭右开写法天然免疫这个问题因为 right 0left 0循环条件不成立直接跳过。所以我建议无论哪种写法都先判断一下len(nums) 0的情况至少心里有数。第五个坑模版背串了。这是最让我哭笑不得的坑。有些人左闭右闭和左闭右开的代码各写了一遍结果第二天再写把right len(nums)的初始值跟while left right的循环条件搭配在一起。想想看right 初始为 6left 为 0第一次循环 mid 3一切正常但后续如果收缩到 right 2而 left 也变成 22 2成立进入循环mid 2此时访问 nums[2] 没问题可如果再收缩一次left 3right 23 2不成立循环退出。看似不会死循环但逻辑上区间定义已经混乱某些场景下就会出问题。最典型的错误是数组长度为 1 时right 1left 0mid 0nums[0] target 时 right mid 0此时 left 0right 00 0成立进入循环mid 0nums[0] targetright mid 0于是又进入循环——死循环出现了。所以两种写法一定要分开记不要贪图省事各取一半。5. 二分查找的进阶方向从 704 到更多变体5.1 寻找左边界与右边界重复元素的处理704 题明确说了数组中无重复元素所以只需要返回唯一匹配的下标。但实际工程中重复元素非常常见比如一个列表里有很多相同的时间戳、相同价格的订单。这时候需要的不再是“找一个等于目标值的位置”而是“找第一个等于目标值的位置”或者“找最后一个等于目标值的位置”。寻找左边界的思想很简单即使nums[mid] target也不急着返回而是把搜索区间进一步向左压缩看看左边还有没有相等的元素。代码如下def search_left(nums, target): left, right 0, len(nums) # 左闭右开 while left right: mid left (right - left) // 2 if nums[mid] target: right mid else: left mid 1 return left这段代码的精髓在于nums[mid] target时mid可能是答案也可能答案在更左边所以不能排除mid只能把右边界收缩到mid本身。循环结束时left指向第一个不小于target的位置。如果这个位置存在且值等于target就是左边界否则说明目标值不存在。搜索右边界则反过来nums[mid] target时左边界收缩为mid 1循环结束后left - 1就是最后一个等于target的位置。这两个变体在面试中出现频率极高很多候选人能默写出常规二分但一到重复元素场景就开始混乱。建议你在把 704 题吃透后立刻找两道边界题练手比如在排序数组中查找元素的第一个和最后一个位置LeetCode 34 题用上面的思路去解会顺畅很多。5.2 旋转数组与二维矩阵二分思想的延伸除了边界查找二分思想还能解决两类看起来很不一样的题。第一类是旋转有序数组比如原数组 [0,1,2,4,5,6,7] 在某处截断后重排成 [4,5,6,7,0,1,2]仍然可以用二分查找。思路不是对整个数组做一次完整二分而是每次判断哪一半是有序的然后在有序的那一半里决定下一步方向。这题之所以经典是因为它考察的是对数组“部分有序”特性的利用而不是死板的全局有序。第二类是在有序二维矩阵中查找目标值比如每一行从左到右递增、每一列从上到下递增的矩阵。一种做法是从右上角开始每次比较当前元素与目标值如果目标值更小就向左移动更大就向下移动时间复杂度和二分接近思路本质上也是每次排除一行或一列。这两类题目都有一个共同点核心不是“用二分查找”而是“利用有序性做区间收缩”。理解了 704 题的区间不变量思想再看这些题目你会发现套路是相通的无非是搜索空间的形状变了。5.3 我自己刷完 704 之后的体会说几句不中听但实在的话。二分查找是算法基础里性价比最高的一道题之一但也是最容易让人产生“我懂了”错觉的一道题。我见过不少工作多年的开发者在写二分时翻车原因就是长期没写、边界条件记不清。所以我建议你把 704 题的两种写法都背下来不是背代码而是背“区间定义的规则”然后每周抽时间手写一遍保持手感。我个人在面试别人时最常问的二分题目就是 704 题变形。不是因为它难而是因为它能快速筛选出两类人一类是真懂边界条件的人另一类是背范文的人。问几个问题就知道了——为什么循环条件是小于而不是小于等于当 nums[mid] 小于 target 时left 为什么是 mid 1 而不是 mid你如何用循环不变量证明你的算法会终止能答上这几个问题才是真正掌握了。最后分享一个实用的小技巧调试二分查找时不要只看最终的输出对不对而是在每次循环里打印 left、right、mid 和 nums[mid] 四个值观察区间是怎么收缩的。如果你发现自己某一步收缩后的区间比上一步还大或者区间变成了负数范围那一定某个边界更新出错了。这个调试习惯帮我节省了大量时间也让我在写其他二分变体时更快定位问题。建议你下次刷题时也试试。
二分查找深度解析：边界条件与循环不变量一次讲透
1. 为什么一道二分查找值得单独写一篇做了九天算法打卡前八天都在跟数组的基本遍历、插入、删除打交道到了第四天正式开始接触第一种真正意义上的查找算法。704这道题题面一句话就能看完给定一个升序整数数组和一个目标值返回目标值在数组中的下标不存在就返回 -1。看起来简单但二分查找恰恰是那种“一看就会、一写就错”的典型。网上关于这道题的讨论常年不断核心分歧就集中在两点循环条件到底用left right还是left right更新边界时mid到底要不要加一减一。这两个问题不搞清楚代码就是改来改去碰运气。这道题适合谁来学两种人。第一种是刚接触算法题的新手需要从这道题建立起“边界意识”——写任何算法题边界条件往往是正确性的关键第二种是已经刷过一阵但总是卡在二分变体题的人比如在旋转数组里找最小值、在有序矩阵里找目标值这些进阶题追根溯源底层都是 704 题的区间控制逻辑。把这道题吃透后面很多看似复杂的题都会豁然开朗。我在实际刷题时最大的感受是二分查找考的不是“懂不懂原理”而是“能不能把区间的定义贯彻到底”。很多人写错不是不知道二分的思想而是写代码的过程中区间的含义悄悄变了。所以这篇文章我会从原理开始讲起重点放在两种主流写法上最后附上我自己的调试记录和常见坑点尽量让你一次性把这道题写稳。2. 二分查找的前提条件与核心思想2.1 有序数组为什么是硬性要求二分查找的第一个前提是数据必须存储在数组中也就是支持通过下标随机访问第二个前提是数组本身具备单调性通常是升序。这两个前提缺一个都不行。先说说“有序”。二分查找的每一步都在做一件事拿中间元素跟目标值比然后砍掉一半不可能的区域。这个过程能成立依赖于一个关键逻辑——如果目标值比中间元素大那么目标值一定在右半边如果目标值比中间元素小那么目标值一定在左半边。这个“一定”从哪里来就是从数组的有序性来的。只有数组有序你才能确信中间元素左侧的所有元素都不大于它右侧的所有元素都不小于它。假如数组是无序的中间元素比目标值小目标值完全可能出现在左半边因为你根本不知道左边有哪些数砍掉左半边就会漏掉答案。很多人初学时会忽略一个细节这里说的有序默认是升序。但实际工作中遇到的数组也可能是降序的比如按时间倒序排列的日志列表。降序数组同样可以用二分查找只是判断逻辑要反过来——中间元素比目标值小那答案在左边中间元素比目标值大答案在右边。我建议在学习阶段就把升序和降序的写法都练一遍因为这能帮你摆脱“背模板”的坏习惯真正理解每一步判断的依据。再来说说“随机访问”。“随机”这个词在这里不是“随机数”的意思而是指可以不依赖顺序、直接跳到任意位置访问元素。数组在内存里是一段连续空间知道下标就能直接算出内存地址访问时间恒定为 O(1)。但链表就不行链表虽然也是线性结构可它每个节点只知道自己下一个邻居的位置想拿到第 n 个节点必须从头一个个走过去时间复杂度是 O(n)。如果数据结构是链表二分查找每次取中间元素都要遍历整个链表一次 O(n)二分 O(logn) 次总复杂度退化到 O(nlogn)比直接一遍线性查找还慢。这也是为什么二分查找几乎总是跟“数组”绑定出现。2.2 折半搜索的本质每次排除一半二分查找的时间复杂度是 O(logn)这在算法题里是一个非常诱人的数字。直观感受一下一个长度为 100 万的升序数组线性查找最坏需要比较 100 万次而二分查找最多比较 20 次左右因为 2 的 20 次方正好超过 100 万。数据规模每翻一倍二分查找只多一次比较这种增长曲线在数据量大的时候优势极其明显。每次比较能排除一半区域这个逻辑可以用一个生活化的例子理解。比如你在看一本 1000 页的书知道里面某一页有个词但你不知道页码。你不会从第 1 页开始逐页翻而是先翻到中间第 500 页看看这个词是在左边还是右边如果判断在左边就翻到第 250 页继续找。每一步都把搜索范围缩小一半最多翻十次左右就能找到。二分查找在数组上做的事完全一样。但我必须提醒一点二分查找的 O(logn) 只体现在“比较的次数”上。实际工程里数组的访问速度和比较操作的常数因子也很重要。在小规模数据下比如数组长度只有几十二分查找和线性查找的耗时差距几乎感觉不到甚至还可能因为分支判断更多而略慢。所以工程上不要无脑二分通常数组规模在几百以下时线性查找的可读性和简洁性更值得优先考虑。算法题的训练价值在于建立复杂度思维但落地到项目里还要结合真实数据规模做权衡。2.3 循环不变量的概念整个算法的灵魂二分查找最抽象也最关键的概念是“循环不变量”。这个词听起来吓人但理解起来并不难它指的是在循环执行的每一步某个条件始终成立。对于二分查找这个不变量就是——你定义的搜索区间里一定包含可能的目标值位置。换句话说你在写代码之前要明确一个具体规则我维护的这个[left, right]区间代表的是“目标值可能存在的位置”。每次循环结束收缩区间时都必须保证新的[left, right]依然满足这个语义。很多人写错就是因为收缩区间时把可能包含答案的位置排除掉了或者把已经排除掉的位置又重新包含进来导致循环不变量被破坏。举个例子如果你定义的是左闭右闭区间也就是left和right都包含在搜索范围内那么当你判断nums[mid] target时说明mid这个位置以及它左边的所有位置都不可能存在目标值下一步应该把left更新为mid 1。但如果此时你把left更新成mid那么mid这个已经确认不等于目标值的位置又回到了搜索区间里虽然这次不会出错但会破坏不变量最终可能导致死循环。所以写二分查找之前先在纸上写下这句话“我维护的区间范围到底包含哪些位置”把这个定义写清楚再动手写代码边界条件就会变得水到渠成。这不是玄学而是很多高级程序员在代码评审时一定会追问的问题。3. 704 题完整解题两种区间写法的细节对比3.1 题目原文与关键约定题目给的是一个升序整数数组nums和一个整数target要求在数组中找到target的下标如果不存在则返回 -1。题目还明确说数组中的元素是唯一的这个条件很重要它意味着不存在“重复元素该返回哪一个下标”的歧义。前置条件是这样的项目说明输入升序整数数组 nums、目标值 target输出target 的下标不存在时返回 -1条件数组中无重复元素示例nums [-1,0,3,5,9,12]target 9输出 4边界nums 长度可为 0target 可能小于最小元素或大于最大元素在动手写代码前先想清楚几个边界场景数组长度为零的情况、目标值比所有元素都小、目标值比所有元素都大、目标值刚好在数组最左侧或最右侧。这四个场景在代码里都必须能正确结束循环并返回 -1 或正确下标。3.2 左闭右闭写法最直观、最好理解第一种写法也是最推荐新手掌握的写法是左闭右闭区间。所谓“左闭右闭”就是left指向搜索区间的第一个位置right指向搜索区间的最后一个位置区间写作[left, right]。这意味着left和right指向的位置本身也在搜索范围内。代码如下使用 Pythondef search(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid - 1 return -1为什么循环条件是left right因为当left right时[left, right]区间里还剩一个元素这个元素还没有被比较过它仍然可能是目标值。所以只要left right循环就必须继续。如果你写成left right那么当左右指针相遇时会直接跳出循环最后一个元素没有检查答案就被漏掉了。为什么nums[mid] target时要把left更新成mid 1因为mid这个位置的元素已经确认小于目标它自己肯定不是答案同时有序性决定了它左边的元素也都小于它更不可能等于目标值。所以可以安全地把左边界收缩到mid 1把mid及左侧全部排出去。对称地nums[mid] target时right mid - 1也是同理。这种写法我在讲解时最喜欢用因为它和人的直觉一致区间有明确的头尾挨个排除就好。只要保持“区间内每个元素都还没被比较过”这个心态边界条件就不会写错。3.3 左闭右开写法工程中更常见的风格第二种写法是左闭右开区间区间写作[left, right)。注意right指向的不是搜索区间的最后一个元素而是“最后一个元素的下一个位置”。搜索区间实际包含的是left到right - 1这些位置。def search(nums, target): left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid return -1这种写法和左闭右闭有两个关键区别。第一个区别是初始值right初始为len(nums)而不是len(nums) - 1因为right本身不包含在搜索区间内所以它可以等于数组长度。这样写还有一个好处如果数组为空right初始为 0left也是 0left right不成立循环直接跳过返回 -1不用单独处理空数组。第二个区别是循环条件写成left right。为什么这里不用因为当left right时区间[left, right)是空的已经没有元素可以搜索了。空区间意味着搜索结束所以循环条件严格小于即可。如果写成当左右相等时还会再进入一次循环此时 mid 等于 left 也等于 rightmid 不在区间内访问nums[mid]可能越界这是初学者容易踩的坑。第三个区别是收缩边界的方式当nums[mid] target时right mid而不是mid - 1。原因是区间右端是开区间right不参与搜索把right设为mid就把mid及右侧全部排除了——mid已经不等于目标值它不该留在区间里而右开区间本来就不包含right指向的位置所以mid被自然排除。如果写成right mid - 1那mid - 1也会被排除而mid - 1这个位置还没被比较过可能包含目标值就被错误地丢掉了。两种写法各有拥护者。我的个人建议是左闭右闭适合学习和面试时讲解逻辑直观、不容易丢答案左闭右开在 C 的 STL 标准库和很多工程代码里更常见因为迭代器的end()普遍是开区间。但无论你用哪种最重要的是把区间定义写清楚不要混用。很多人写着写着就把两种写法的细节混在一起比如用左闭右闭的初始值搭配左闭右开的循环条件结果各种莫名其妙的问题。3.4 两种写法的对比与选择建议对比项左闭右闭 [left, right]左闭右开 [left, right)初始值left 0, right len(nums) - 1left 0, right len(nums)循环条件left rightleft right区间为空的条件left rightleft rightmid 偏大时更新right mid - 1right midmid 偏小时更新left mid 1left mid 1空数组处理需要特判 left right循环自动跳过推荐场景面试、初学工程代码、C 迭代器风格我在实战中遇到过很多次面试者两种写法来回切换的情况。面试官问“为什么循环条件是小于等于”回答“因为要保证区间不为空”这种答案没问题。但再问一句“你的区间是左闭右闭还是左闭右开”很多人就开始含糊了。这恰恰说明很多人的二分查找是背下来的而不是理解下来的。想真正掌握建议你分别用两种写法各写一遍然后用同样的测试用例跑一遍感受一下边界收缩的差异这套功夫值得花。4. 实操过程从读题到 AC 的完整记录4.1 测试用例的设计思路写代码前先设计测试用例这是一个被很多人忽略的好习惯。不要一上来就提交而是先在本地把下面这些场景过一遍。这是我刷 704 题时实际用的一组测试用例测试场景numstarget期望结果说明目标在中间[1,2,3,4,5]32常规场景目标在最左[1,2,3,4,5]10左边界目标在最右[1,2,3,4,5]54右边界目标不存在偏小[1,2,3,4,5]0-1小于所有元素目标不存在偏大[1,2,3,4,5]6-1大于所有元素目标不存在在中间[1,2,3,4,5]7-1落在数值区间内但不存在的数空数组[]1-1边界场景单元素命中[1]10单元素成功单元素未命中[1]2-1单元素失败两个元素[1,2]21最小规模的多元素场景这组用例覆盖了二分查找的几乎所有边界。我强烈建议你在本地把这组用例跑通后再提交。很多时候你以为自己代码写对了一提交发现超时或者报错问题往往不是“二分查找不会”而是某个边界场景没有覆盖到。4.2 逐行推演一遍循环过程以左闭右闭写法为例手动推演一个完整过程。数组 nums [-1,0,3,5,9,12]target 9。初始状态left 0right 5搜索区间 [0,5]包含全部 6 个元素。第一次循环mid 0 (5 - 0) // 2 2nums[2] 3。3 9说明目标值在右侧把 left 更新为 3。此时区间变为 [3,5]包含位置 3、4、5。第二次循环mid 3 (5 - 3) // 2 4nums[4] 9。9 等于目标值直接返回 4。整个过程只比较了两次。如果 target 9 而数组长度变成 100 万也只需要约 20 次比较这就是二进制对数的威力。再看一个目标不存在的情况。target 7同样的数组。第一次循环mid 2nums[2] 33 7left 3。第二次循环mid 4nums[4] 99 7right 3。此时 left 3right 3区间 [3,3] 不为空继续循环。第三次循环mid 3nums[3] 55 7left 4。此时 left 4right 3区间为空循环条件left right不成立跳出循环返回 -1。注意一个细节在这种写法下循环结束后 left 和 right 的关系有两种可能要么 left right 1要么 left 指向第一个大于 target 的位置。这为二分查找的变体题提供了伏笔比如寻找插入位置时循环结束后的 left 往往就是答案。现在不需要深究但可以留个心眼。4.3 常见错误与排查技巧实录我总结了自己踩过的坑也看过不少初学者犯的错集中排在前几位的是下面这些。第一个坑循环条件写错导致死循环或漏解。最常见的是左闭右闭写法里用了left right结果当数组长度为 1 且目标值就是那唯一一个元素时left 和 right 初始都为 0循环条件不满足直接返回 -1。排查方法很简单在纸上画出区间收缩过程每次都问自己“当前区间还剩哪些位置没查过”如果 left right 但那个位置还没查过那循环条件就有问题。第二个坑mid 计算溢出。早期教科书会写mid (left right) // 2。这个写法在 left 和 right 都很小的时候没问题但当数组长度接近编程语言中整型最大值的一半时left right可能溢出导致 mid 变成负数或错误的大数。工程上标准写法是mid left (right - left) // 2先算差值再除以二从根源上避免溢出。虽然刷题时数组长度很少那么大但养成这个习惯没有坏处而且这个写法在变体题里一样适用。第三个坑收缩区间时把答案排除了。这个坑特别隐蔽。左闭右开写法中当nums[mid] target时有人写成right mid - 1导致mid - 1这个还没比较过的位置被排除。如果正确答案恰好就在mid - 1结果就错了。排查这类问题的方法是每次收缩后在草稿纸上重新画一遍区间确认区间里包含的所有位置都还没有被排除。第四个坑忘记处理空数组。左闭右闭写法中right len(nums) - 1如果数组为空right 初始为 -1循环条件left right也就是0 -1不成立不会进入循环其实也能返回 -1。但如果你在循环前就访问了nums[0]或者对 right 做了其他操作就会有越界风险。左闭右开写法天然免疫这个问题因为 right 0left 0循环条件不成立直接跳过。所以我建议无论哪种写法都先判断一下len(nums) 0的情况至少心里有数。第五个坑模版背串了。这是最让我哭笑不得的坑。有些人左闭右闭和左闭右开的代码各写了一遍结果第二天再写把right len(nums)的初始值跟while left right的循环条件搭配在一起。想想看right 初始为 6left 为 0第一次循环 mid 3一切正常但后续如果收缩到 right 2而 left 也变成 22 2成立进入循环mid 2此时访问 nums[2] 没问题可如果再收缩一次left 3right 23 2不成立循环退出。看似不会死循环但逻辑上区间定义已经混乱某些场景下就会出问题。最典型的错误是数组长度为 1 时right 1left 0mid 0nums[0] target 时 right mid 0此时 left 0right 00 0成立进入循环mid 0nums[0] targetright mid 0于是又进入循环——死循环出现了。所以两种写法一定要分开记不要贪图省事各取一半。5. 二分查找的进阶方向从 704 到更多变体5.1 寻找左边界与右边界重复元素的处理704 题明确说了数组中无重复元素所以只需要返回唯一匹配的下标。但实际工程中重复元素非常常见比如一个列表里有很多相同的时间戳、相同价格的订单。这时候需要的不再是“找一个等于目标值的位置”而是“找第一个等于目标值的位置”或者“找最后一个等于目标值的位置”。寻找左边界的思想很简单即使nums[mid] target也不急着返回而是把搜索区间进一步向左压缩看看左边还有没有相等的元素。代码如下def search_left(nums, target): left, right 0, len(nums) # 左闭右开 while left right: mid left (right - left) // 2 if nums[mid] target: right mid else: left mid 1 return left这段代码的精髓在于nums[mid] target时mid可能是答案也可能答案在更左边所以不能排除mid只能把右边界收缩到mid本身。循环结束时left指向第一个不小于target的位置。如果这个位置存在且值等于target就是左边界否则说明目标值不存在。搜索右边界则反过来nums[mid] target时左边界收缩为mid 1循环结束后left - 1就是最后一个等于target的位置。这两个变体在面试中出现频率极高很多候选人能默写出常规二分但一到重复元素场景就开始混乱。建议你在把 704 题吃透后立刻找两道边界题练手比如在排序数组中查找元素的第一个和最后一个位置LeetCode 34 题用上面的思路去解会顺畅很多。5.2 旋转数组与二维矩阵二分思想的延伸除了边界查找二分思想还能解决两类看起来很不一样的题。第一类是旋转有序数组比如原数组 [0,1,2,4,5,6,7] 在某处截断后重排成 [4,5,6,7,0,1,2]仍然可以用二分查找。思路不是对整个数组做一次完整二分而是每次判断哪一半是有序的然后在有序的那一半里决定下一步方向。这题之所以经典是因为它考察的是对数组“部分有序”特性的利用而不是死板的全局有序。第二类是在有序二维矩阵中查找目标值比如每一行从左到右递增、每一列从上到下递增的矩阵。一种做法是从右上角开始每次比较当前元素与目标值如果目标值更小就向左移动更大就向下移动时间复杂度和二分接近思路本质上也是每次排除一行或一列。这两类题目都有一个共同点核心不是“用二分查找”而是“利用有序性做区间收缩”。理解了 704 题的区间不变量思想再看这些题目你会发现套路是相通的无非是搜索空间的形状变了。5.3 我自己刷完 704 之后的体会说几句不中听但实在的话。二分查找是算法基础里性价比最高的一道题之一但也是最容易让人产生“我懂了”错觉的一道题。我见过不少工作多年的开发者在写二分时翻车原因就是长期没写、边界条件记不清。所以我建议你把 704 题的两种写法都背下来不是背代码而是背“区间定义的规则”然后每周抽时间手写一遍保持手感。我个人在面试别人时最常问的二分题目就是 704 题变形。不是因为它难而是因为它能快速筛选出两类人一类是真懂边界条件的人另一类是背范文的人。问几个问题就知道了——为什么循环条件是小于而不是小于等于当 nums[mid] 小于 target 时left 为什么是 mid 1 而不是 mid你如何用循环不变量证明你的算法会终止能答上这几个问题才是真正掌握了。最后分享一个实用的小技巧调试二分查找时不要只看最终的输出对不对而是在每次循环里打印 left、right、mid 和 nums[mid] 四个值观察区间是怎么收缩的。如果你发现自己某一步收缩后的区间比上一步还大或者区间变成了负数范围那一定某个边界更新出错了。这个调试习惯帮我节省了大量时间也让我在写其他二分变体时更快定位问题。建议你下次刷题时也试试。
