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 长度可为 0，target 可能小于最小元素或大于最大元素 |
在动手写代码前，先想清楚几个边界场景：数组长度为零的情况、目标值比所有元素都小、目标值比所有元素都大、目标值刚好在数组最左侧或最右侧。这四个场景在代码里都必须能正确结束循环并返回 -1 或正确下标。
3.2 左闭右闭写法：最直观、最好理解
第一种写法，也是最推荐新手掌握的写法，是左闭右闭区间。所谓“左闭右闭”，就是left指向搜索区间的第一个位置，right指向搜索区间的最后一个位置，区间写作[left, right]。这意味着left和right指向的位置本身也在搜索范围内。
代码如下，使用 Python：
def 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初始为 0，left也是 0，left < right不成立，循环直接跳过，返回 -1，不用单独处理空数组。
第二个区别是循环条件：写成left < right。为什么这里不用<=？因为当left == right时，区间[left, right)是空的，已经没有元素可以搜索了。空区间意味着搜索结束，所以循环条件严格小于即可。如果写成<=，当左右相等时还会再进入一次循环，此时 mid 等于 left 也等于 right，mid 不在区间内，访问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) - 1 | left = 0, right = len(nums) |
| 循环条件 | left <= right | left < right |
| 区间为空的条件 | left > right | left == right |
| mid 偏大时更新 | right = mid - 1 | right = mid |
| mid 偏小时更新 | left = mid + 1 | left = mid + 1 |
| 空数组处理 | 需要特判 left > right | 循环自动跳过 |
| 推荐场景 | 面试、初学 | 工程代码、C++ 迭代器风格 |
我在实战中遇到过很多次面试者两种写法来回切换的情况。面试官问“为什么循环条件是小于等于”，回答“因为要保证区间不为空”，这种答案没问题。但再问一句“你的区间是左闭右闭还是左闭右开”，很多人就开始含糊了。这恰恰说明，很多人的二分查找是背下来的，而不是理解下来的。想真正掌握，建议你分别用两种写法各写一遍，然后用同样的测试用例跑一遍，感受一下边界收缩的差异，这套功夫值得花。
4. 实操过程：从读题到 AC 的完整记录
4.1 测试用例的设计思路
写代码前先设计测试用例，这是一个被很多人忽略的好习惯。不要一上来就提交，而是先在本地把下面这些场景过一遍。这是我刷 704 题时实际用的一组测试用例：
| 测试场景 | nums | target | 期望结果 | 说明 |
|---|---|---|---|---|
| 目标在中间 | [1,2,3,4,5] | 3 | 2 | 常规场景 |
| 目标在最左 | [1,2,3,4,5] | 1 | 0 | 左边界 |
| 目标在最右 | [1,2,3,4,5] | 5 | 4 | 右边界 |
| 目标不存在（偏小） | [1,2,3,4,5] | 0 | -1 | 小于所有元素 |
| 目标不存在（偏大） | [1,2,3,4,5] | 6 | -1 | 大于所有元素 |
| 目标不存在（在中间） | [1,2,3,4,5] | 7 | -1 | 落在数值区间内但不存在的数 |
| 空数组 | [] | 1 | -1 | 边界场景 |
| 单元素命中 | [1] | 1 | 0 | 单元素成功 |
| 单元素未命中 | [1] | 2 | -1 | 单元素失败 |
| 两个元素 | [1,2] | 2 | 1 | 最小规模的多元素场景 |
这组用例覆盖了二分查找的几乎所有边界。我强烈建议你在本地把这组用例跑通后再提交。很多时候你以为自己代码写对了，一提交发现超时或者报错，问题往往不是“二分查找不会”，而是某个边界场景没有覆盖到。
4.2 逐行推演一遍循环过程
以左闭右闭写法为例，手动推演一个完整过程。数组 nums = [-1,0,3,5,9,12]，target = 9。
初始状态：left = 0，right = 5，搜索区间 [0,5]，包含全部 6 个元素。
第一次循环：mid = 0 + (5 - 0) // 2 = 2，nums[2] = 3。3 < 9，说明目标值在右侧，把 left 更新为 3。此时区间变为 [3,5]，包含位置 3、4、5。
第二次循环：mid = 3 + (5 - 3) // 2 = 4，nums[4] = 9。9 等于目标值，直接返回 4。
整个过程只比较了两次。如果 target = 9 而数组长度变成 100 万，也只需要约 20 次比较，这就是二进制对数的威力。
再看一个目标不存在的情况。target = 7，同样的数组。
第一次循环：mid = 2，nums[2] = 3，3 < 7，left = 3。
第二次循环：mid = 4，nums[4] = 9，9 > 7，right = 3。
此时 left = 3，right = 3，区间 [3,3] 不为空，继续循环。
第三次循环：mid = 3，nums[3] = 5，5 < 7，left = 4。
此时 left = 4，right = 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 = 0，left = 0，循环条件不成立，直接跳过。所以我建议无论哪种写法，都先判断一下len(nums) == 0的情况，至少心里有数。
第五个坑：模版背串了。
这是最让我哭笑不得的坑。有些人左闭右闭和左闭右开的代码各写了一遍，结果第二天再写，把right = len(nums)的初始值跟while left <= right的循环条件搭配在一起。想想看：right 初始为 6，left 为 0，第一次循环 mid = 3，一切正常；但后续如果收缩到 right = 2，而 left 也变成 2，2 <= 2成立，进入循环，mid = 2，此时访问 nums[2] 没问题；可如果再收缩一次，left = 3，right = 2，3 <= 2不成立，循环退出。看似不会死循环，但逻辑上区间定义已经混乱，某些场景下就会出问题。最典型的错误是数组长度为 1 时，right = 1，left = 0，mid = 0，nums[0] > target 时 right = mid = 0，此时 left = 0，right = 0，0 <= 0成立，进入循环，mid = 0，nums[0] > target，right = 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] 四个值，观察区间是怎么收缩的。如果你发现自己某一步收缩后的区间比上一步还大，或者区间变成了负数范围，那一定某个边界更新出错了。这个调试习惯帮我节省了大量时间，也让我在写其他二分变体时更快定位问题。建议你下次刷题时也试试。
