在面试和实际工程里二分查找是那种“一看就会一写就废”的典型代表。LeetCode 704这道题表面上是让你在一个有序数组里找目标值实际上考的是你对循环不变量、边界收缩和终止条件的理解到底透不透。我见过太多候选人能把思路讲得头头是道一上手写代码就在while条件或者mid更新上栽跟头。这篇文章不打算讲那些虚的头头是道的理论直接拿704这道题做靶子把二分查找掰开揉碎从最基础的数组场景讲到各种变体把那些文档里不会写、面试时却容易踩的坑全部摊开给你看。无论你是刚开始刷题的新手还是准备跳槽想巩固基础的老手这篇文章都能帮你把二分查找这块硬骨头啃下来。1. 二分查找的核心思路与适用场景1.1 为什么有序数组让查找变快了先想一个最朴素的问题给你一个按升序排列的数组让你找一个数你会怎么找最直接的办法就是从第一个元素开始挨个比对找到就返回下标找不到就返回-1。这种方法叫线性查找时间复杂度O(n)。在数据量小的时候无所谓但如果数组里有上亿个元素线性查找的代价就非常可观了。二分查找的思路完全不同。它利用了一个关键信息数组是有序的。既然有序那么中间位置的元素就天然地把数组分成了左右两半。如果目标值比中间元素小那目标值只可能出现在左半边右半边可以整个丢掉如果目标值比中间元素大那目标值只可能出现在右半边左半边可以整个丢掉。每比较一次搜索范围就缩小一半。这就是二分查找的核心逻辑每次淘汰一半不可能的区域。所以它的时间复杂度是O(log n)。举个例子2的10次方是10242的20次方是1048576。也就是说在100万个有序元素里找一个数线性查找最多需要100万次比较而二分查找最多只需要20次。这个差距在数据量大的时候是降维打击。1.2 二分查找不是“只能用在数组里”很多人觉得二分查找就是“有序数组里查下标”这个认知太窄了。二分查找的本质是“在一个满足单调性的搜索空间里不断缩小范围以逼近目标”。这个搜索空间可以是一个数组也可以是一个函数的值域甚至可以是一个抽象的“可行解区间”。举个例子LeetCode 875题“爱吃香蕉的狒狒”就是典型的二分查找应用它不是在数组里找数而是在“吃香蕉的速度”这个值域里做二分。还有LeetCode 69题求x的平方根本质上是在0到x这个整数区间里二分查找一个数使得它的平方不超过x。再比如查找第一个坏版本LeetCode 278搜索空间是版本号序列目标是从第一个坏版本开始划分的边界。如果理解了这一层你会发现二分查找是很多看似不相关问题的通用解法。它的适用条件是搜索空间具有单调性。所谓单调就是“某个判断条件的结果在搜索空间上是连续的true和连续的false”或者“连续的false和连续的true”这时你就可以用二分查找找到那个边界翻转的位置。1.3 LeetCode 704到底在考什么回到704这道题本身它的题目描述非常简洁给定一个n个元素有序的升序整型数组nums和一个目标值target写一个函数搜索nums中的target如果目标值存在返回下标否则返回-1。这道题标注的难度是“简单”但它的“简单”是建立在你对二分查找各种细节都门儿清的基础上的。很多人做这道题的时候思路是对的也能跑通但要问为什么while里写left right而不是left right为什么right mid - 1而不是right mid就解释不清楚了。这正是面试官最爱追问的地方。所以不要把704当成一道“背模板”的题。它真正的价值是检验你能否严谨地处理边界问题。后面的章节我会从最标准的写法讲起逐步展开区间开闭、边界更新的来龙去脉把这些细节彻底讲透。2. 从零开始手写完整实现2.1 最标准的左闭右闭写法直接给出最经典、最不容易出错的写法也就是left和right都指向有效下标区间是左闭右闭的[left, right]。我用Python演示逻辑在所有语言里完全一致。class Solution: def search(self, nums: List[int], target: int) - int: 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 0, len(nums) - 1初始化时left指向数组第一个元素right指向数组最后一个元素此时区间[left, right]覆盖了整个数组而且两端都是闭合的也就是说left和right指向的元素都可能被检查到。再看while left right循环的终止条件是left大于right也就是搜索区间为空。为什么需要用而不是因为在左闭右闭区间里left等于right时区间内还有一个元素需要检查。比如[3, 3]这个区间中间只有一个下标3如果循环条件是left right这个元素就会被漏掉从而错过target恰好在这个位置的情况。2.2 mid的计算为什么要写成left (right - left) // 2这里有个非常关键的细节mid left (right - left) // 2。为什么不直接写mid (left right) // 2原因有两个。第一个是防止整数溢出。在C或Java这类语言里如果left和right都很大left加上right可能会超出int类型的取值范围导致溢出变成负数程序直接出bug。虽然Python的整数不会溢出但作为一个合格的程序员写出防溢出的写法是职业习惯。用left (right - left) // 2就彻底避免了left right的溢出风险。第二个原因是代码的通用性。如果你以后写C、Java、Go这个写法直接照搬不用担心溢出问题。我见过不少人在牛客网或者LeetCode上遇到“运行结果错误”的用例排查半天发现是mid计算溢出导致的非常冤。第二种常见的mid计算写法是mid left ((right - left) 1)用位运算代替除以2效率更高一些。在Python里两种写法性能差距可以忽略但在C里位运算会稍微快一点。我个人推荐位运算写法特别是在高频调用的场景下能省一点是一点。2.3 left和right的更新为什么是mid加一减一这是二分查找最容易出错的地方。在左闭右闭的写法里当nums[mid] target时说明目标值在mid的右侧而且mid这个位置本身已经被排除了所以下一次搜索的左边界应该是mid 1。同理当nums[mid] target时说明目标值在mid的左侧mid本身被排除右边界更新为mid - 1。这个地方的逻辑一定要想清楚mid这个位置已经和target比较过了不相等所以它不可能成为答案。既然不可能那新的搜索区间就必须把mid排除掉。所以一定是mid 1或mid - 1而不是mid。如果这里写成left mid或right mid会遇到两个问题。第一如果数组里不存在target循环可能陷入死循环。因为当left和right相邻时mid会取到left的位置如果此时nums[mid] target且你执行left midleft会原地不动永远无法收敛。第二即使不死循环也会多做一些无意义的比较逻辑上不干净。3. 左闭右开与区间模板的全面对比3.1 左闭右开写法的完整实现除了左闭右闭另一种常见的写法是左闭右开区间表示为[left, right)其中right指向的元素不在搜索范围内。这种写法在C的STL里非常常见比如std::lower_bound和std::upper_bound都采用这种区间约定。它的代码如下class Solution: def search(self, nums: List[int], target: int) - int: 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循环条件是left right右边界更新是right mid而不是right mid - 1。这三个变化是联动的不能只记其中一个。为什么右边界更新是right mid因为区间是左闭右开的right本身不参与搜索。当nums[mid] target时mid这个位置被排除但mid左边的位置仍然可能包含答案。新的搜索区间应该是不包含mid的[left, mid)所以right更新为mid。由于right不参与搜索把right设成mid就等价于排除了mid这个位置而且不会漏掉mid之前的任何元素。3.2 开闭区间的本质区别与选择建议左闭右闭和左闭右开本质上没有优劣之分只是两种不同的区间约定。但选定一种约定之后所有的边界处理都必须严格遵循该约定否则代码就会出现隐蔽的bug。我把两种写法的关键差异整理成一张表方便你对照记忆对比维度左闭右闭 [left, right]左闭右开 [left, right)初始化rightlen(nums) - 1len(nums)循环条件left rightleft right左边界更新left mid 1left mid 1右边界更新right mid - 1right mid循环终止时left与right关系left rightleft right空区间条件left rightleft right从我的经验来看新手更适合从“左闭右闭”开始学因为它的直观性更强left和right都指向真实存在的元素边界更新是“排除mid”逻辑上比较好理解。当你把左闭右闭写熟练了再去学左闭右开你会发现自己对区间的理解会更深一层。这里多提一句左闭右开在力扣的很多题解里也很常见因为它在某些场景下比如lower_bound查找第一个大于等于target的位置区间定义更优雅。建议你两个模板都熟练掌握面试时根据场景选择就行。但不要两种混着写这是大忌。3.3 为什么说“循环不变量”是理解二分的关键可能你已经发现了上面两种写法的区别归根结底是“循环不变量”不同。所谓循环不变量就是“在循环的每一次迭代开始之前搜索区间到底是什么”。左闭右闭写法的循环不变量是“target如果在数组里一定在区间[left, right]内且left和right都在有效的数组下标范围内”。左闭右开写法的循环不变量是“target如果在数组里一定在区间[left, right)内其中right可以等于数组长度”。每一种边界更新都必须维持这个不变量否则循环进行到一半区间定义就崩了。这个概念听起来有点抽象但它是排查二分查找bug最有力的工具。每次你写完一个二分查找都可以用循环不变量来验证自己是否写对了初始化对不对循环条件对不对每次更新后新的区间是否仍然满足不变量如果都满足算法就是正确的。一旦你的代码跑不正确回到循环不变量去排查通常能找到问题根源。4. 边界条件深入剖析与死循环排查4.1 当target不存在时代码会怎么走学二分查找的时候一个常见的问题是“如果target根本不在数组里循环会不会退出”其实不仅会退出而且退出时left和right的位置关系恰好能告诉你一些有意思的信息。以左闭右闭写法为例。假设数组是[1, 3, 5, 7]target是4。第一次迭代mid 1nums[1] 3 4所以left 2。第二次迭代mid 2nums[2] 5 4所以right 1。此时left 2 right 1循环退出返回-1。注意循环退出时left指向的是第一个大于target的元素的位置。这是一个非常重要的性质很多基于二分查找的变体题目比如求插入位置都依赖这个性质。所以二分查找计算出的不仅仅是“存不存在”它在不存在的时候也能告诉你“应该插入到哪里”。4.2 我调试时遇到的两个典型死循环场景先看第一个场景。如果把循环条件从left right不小心写成left right在左闭右闭的写法下会发生什么当目标值出现在left等于right的那个元素时循环永远不会进入最后一次迭代这个元素永远无法被检查。比如数组[1]target是1left 0right 0循环条件left right直接不成立返回-1但正确答案明明是0。再看第二个场景。如果把左边界更新写成left mid而不是left mid 1会发生什么当数组只有两个元素、target在右侧时left和right会一直卡住。比如数组[1, 3]target是3。初始left 0right 1mid 0nums[0] 1 3执行left mid 0left还是0循环永远不会收敛。这就是典型的死循环bug。排查这类问题有个狠招如果怀疑死循环把mid的取值和每次的left、right打印出来肉眼就能看出问题。对于二分查找这种短代码直接走一遍一两分钟就能定位。4.3 无限逼近与精度损失问题在数组二分里mid是整数所以最终一定会收敛到空区间。但在实数二分里比如二分答案找浮点数解就要考虑精度控制。通常是while (right - left eps)的形式eps是一个足够小的浮点数比如1e-6。这类问题在力扣里不算主流但在某些数学类题目里会出现。思路和整数二分完全一致只不过循环终止条件换成了区间长度小于某个精度阈值。我建议新手先把整数二分搞定浮点二分等需要的时候再补因为逻辑是通用的。5. 二分查找的进阶变体与面试常考扩展5.1 查找左边界与右边界力扣有大量题目是“在有序数组中查找元素的第一个和最后一个位置”LeetCode 34。这道题不能简单地“二分找到mid就返回”而是要找到最左侧的目标值和最右侧的目标值。找左边界的思路是当nums[mid] target时不直接返回而是把right设为mid - 1继续在左侧搜索。当循环结束时left指向的就是第一个等于target的位置如果这个位置不存在说明target不在数组里。找右边界同理当nums[mid] target时更新left为mid 1继续在右侧搜索最终right指向的就是最后一个等于target的位置。这类变体的核心是把“找到等于target的元素”这个条件改写成“找到第一个大于等于target的元素”或“找到最后一个小于等于target的元素”。一旦掌握这个思路很多相关题目都能迎刃而解。5.2 旋转排序数组中的二分另一个高频变体是“搜索旋转排序数组”LeetCode 33。数组本身不是完全有序的但它由两个有序段拼接而成。比如[4, 5, 6, 7, 0, 1, 2]。这种场景下二分查找的关键是判断mid落在左段还是右段然后根据target的位置决定搜索哪一侧。具体做法是先用nums[mid]和nums[left]比较判断当前中点落在哪一段。如果nums[mid] nums[left]说明mid在左段那么左段是严格递增的。此时如果target在[left, mid)之间去左半边找否则去右半边找。如果nums[mid] nums[left]说明mid在右段右段自mid向右是严格递增的。此时如果target在(mid, right]之间去右半边找否则去左半边找。这里有一个常见的陷阱nums[mid] nums[left]的情况如何处理。在无重复元素的旋转排序数组里这个情况基本不会出现但如果题目允许重复元素LeetCode 81就需要退化为线性收缩left指针一次只移动一位。这个细节一定要注意。5.3 二分答案法不只是找数前面提到的“爱吃香蕉的狒狒”是二分答案法的经典例子。题目要求“在H小时内吃掉所有香蕉的最小速度K”暴力解法是遍历所有可能的K从1开始试到最大堆的香蕉数复杂度O(maxPile * n)。用二分答案法则是在[1, maxPile]这个范围上二分查找一个K使得“以速度K能吃完”为真并且K尽可能小。这类题目的判断函数canFinish通常是一个贪心模拟复杂度是O(n)。二分答案法的总复杂度是O(n * log(maxPile))比暴力快一个数量级。遇到这类题目判断标准是问题是否满足“答案的单调性”。比如速度越快越容易吃完时间越短越难完成数值越大越容易满足条件。只要满足这个单调性就可以尝试用二分答案法把“求最优解”转化为“判断某个解是否可行”。6. 常见错题复盘与快速速查表6.1 五个最容易犯的错误我把自己在学习和辅导过程中反复见到的错误做了个汇总基本能覆盖90%以上二分查找写错的情况。第一个是循环条件写错。左闭右闭写成left right导致最后一个元素被漏判。第二个是mid计算溢出。在C和Java里写成(left right) / 2在大数组时溢出。第三个是边界更新写成left mid或right mid导致死循环。第四个是混淆开闭区间把左闭右闭的right更新方式套用到左闭右开上导致区间错误。第五个是没有考虑target不在数组里的情况返回了mid而不是-1。写二分查找的时候每次写完默念三秒钟“我的循环不变量是什么left和right的更新是否维持了不变量”如果能回答上来代码基本不会出问题。6.2 快速自查清单下面的清单建议收藏每次写完二分查找对照检查一遍检查项左闭右闭应满足左闭右开应满足right初始值len(nums) - 1len(nums)while条件left rightleft rightmid值left (right - left) // 2left (right - left) // 2nums[mid] target时left mid 1left mid 1nums[mid] target时right mid - 1right mid循环结束时left/right关系left rightleft right返回值找到返回mid否则-1找到返回mid否则-16.3 实测跑通的完整代码最后附上一段我常用的模板代码用C实现方便你在竞赛或者面试场景直接参考。这段代码我实测过LeetCode 704的全部测试用例稳定通过。class Solution { public: int search(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return -1; } };如果你用的是Java把vectorint换成int[]其他逻辑完全一样。这里再分享一个我自己的习惯写二分查找时先在注释里写清楚区间定义比如// [left, right]、// 左闭右闭然后再写代码。这能有效防止写high了以后把两种模板混在一起。等你养成这个习惯再回头看二分查找会发现它一点都不难难的只是你愿不愿意把边界条件想清楚。我在实际刷题过程中还有一个体会不要贪多把LeetCode 704、34、35、278、33、875这六道题按顺序吃透比盲目刷一百道题更有效。前四道夯实基础后两道引入旋转数组和二分答案覆盖了二分查找的大部分考点。每道题做完以后试着不看模板手写一遍写错就重新来直到一遍通过。这种“刻意练习”的收益非常可观。