代码随想录算法训练营的第一天打卡题目是704.二分查找。坦白说看到这个题目名的时候很多人心里想的是二分查找嘛不就是while循环里挪左右指针我早就会了。但真正动手写起来才发现边界条件搞错、死循环、漏查目标值这些问题一个比一个隐蔽。训练营第一天选这道题其实刻意得很它考察的从来不是会不会写二分而是能不能把区间定义讲清楚这才是算法功底的分水岭。这篇内容我按自己第一天刷题的实际过程来写包含两种主流写法、手动模拟的完整过程、以及我踩过的几个典型坑。无论你是第一次接触二分查找还是写过但总在边界上翻车这一篇都能让你把704吃透顺带把后面35题、34题、69题的套路也摸个大概。1. 训练营第一天为什么偏偏是7041.1 704这道题在算法体系里的位置LeetCode 704题的原题很简洁给定一个升序排列的整数数组nums和一个目标值target找到 target 在数组中的下标找不到就返回-1。题目保证数组中的元素是唯一的这其实已经帮你省掉了最麻烦的重复元素处理让你能专注在二分查找最基本的框架上。算法训练营第一篇选择它道理很直白数组和二分查找是后续所有高频题的地基。你后面遇到的二叉树搜索、有序矩阵查找、旋转数组找最值本质上都是在有序空间里快速缩小搜索范围这个思路上做变形。第一题如果稀里糊涂过去了后面会越写越心虚。反过来如果第一题就把区间定义和边界更新的对应关系刻进脑子后面的题目就是在这个骨架上添肉。从难度阶梯上看704属于典型的看起来简单、写对很难的题。我见过不少刷了两百题的人回头写704照样在边界上纠结。这道题最大的价值不是让你AC然后截图打卡而是逼你回答一个问题你写的每一行边界判断依据是什么1.2 二分查找的应用场景与前置知识二分查找不是银弹它有两个硬性前提数据结构支持随机访问也就是能用下标直接取元素数据在查找维度上是有序的。数组升序是题目给好的条件实战中如果遇到无序数组你得先排序或者自己维护一个有序结构比如有序集合、跳表、二叉搜索树。有个生活化的类比查英文字典时你不会从第一页翻起而是根据目标单词的首字母直接翻到大致区域再根据前后页的字母顺序决定往前翻还是往后翻。每翻一次待查范围就缩小一半。这个缩小一半就是二分查找的核心它让时间复杂度从顺序查找的O(n)降到O(logn)。一个包含100万个元素的有序数组顺序查找最坏要查100万次二分查找最多只需要20次。不过需要注意二分查找的O(logn)是建立在数组随机访问基础上的。如果换成链表即使有序也无法直接用二分因为访问中间节点本身就要遍历这就是为什么后面会看到二分查找与链表结合的题目时解法往往要换成跳表或者二叉树而不是硬套二分。2. 二分查找的核心原理与两种经典写法2.1 循环不变量两种区间的理解二分查找的每一轮循环都必须维护一个明确的前提目标值target只可能存在于当前[left, right]这个范围内。这个范围一旦定义清楚循环里所有条件都要服从它这就是循环不变量。最常见的两种区间定义是左闭右闭[left, right]和左闭右开[left, right)。很多新手纠结的是right到底该不该减一while里到底写left right还是left right这些都不是记忆问题而是区间的数学定义问题。左闭右闭意味着left和right指向的元素都是可能的目标值也就是说搜索范围包含了两个端点。左闭右开意味着right指向的元素不参与搜索它只是超尾哨兵实际搜索范围是[left, right)这个半开半闭区间。这两种定义没有绝对的对错但一旦选定后面的初始化、循环条件、边界更新必须保持一致否则代码必然出错。2.2 mid的求法与整数溢出陷阱mid的经典求法是mid (left right) / 2这个写法在面试里其实是个扣分项。当left和right都很大时两者相加可能超过int类型上限导致溢出变成负数mid一下就飞出去了。更稳妥的写法是mid left (right - left) / 2先算差值再除有效避免溢出。这里有个关于加不加1的细节值得展开说说。当区间只剩两个元素时比如left 3, right 4mid 3 (4 - 3) / 2 3mid会偏向左端点。如果目标值在右端点4上while循环需要在下一轮把left更新为mid 1才能收敛。这个mid偏左、更新left时加1的配合关系在左闭右开写法里也要注意。还有一种写法是mid left (right - left 1) / 2让mid偏向右端点这常见于查找右边界或者避免死循环的场景。初学阶段建议先把偏左的mid用熟后面遇到34题时再灵活切换。2.3 死循环与漏查的根源死循环最常见的原因不是mid求错而是left和right的更新没有让区间严格缩小。比如某个写法里left更新为mid而mid又恰好等于left区间永远不缩小程序就卡死在循环里。另一个常见问题是循环结束后的处理不当循环退出时left可能已经越界直接访问nums[left]会报错必须先判断下标合法性。漏查目标值的根源往往是边界更新时多了一步或者少了一步。比如左闭右开写法里如果发现nums[mid] target应该是left mid 1如果发现nums[mid] target应该是right mid。新手容易把后者写成right mid - 1这样如果目标值正好在mid - 1的位置就被跳过漏掉了。理解这些根源之前背诵代码意义不大。我现在写代码前会先在注释里写清区间定义再逐个写判断分支写完顺手用样例手动模拟一遍基础错误基本都能当场拦住。3. 704.二分查找完整题解与代码实现3.1 题目理解与输入输出分析704的输入约束很友好数组长度n的范围是1到10的4次方元素数值范围在正负10的4次方之间数组严格升序且元素互不重复。返回要求是找到就返回下标找不到返回-1。因为长度最小是1所以不需要单独处理空数组但null的情况在核心代码模式里通常不会出现面试时要留意。手动选一个标准样例来推演nums [-1,0,3,5,9,12]target 9。正确答案是4因为nums[4] 12不对我重新写清楚nums[4] 9下标从0开始所以返回4。这个样例是LeetCode官方给的拿来做手动模拟最合适。还有一个细节需要提前说明题目保证没有重复元素这意味着只需要返回任意一个匹配下标即可。如果数组里有重复元素704的代码会失效因为二分查找默认只找某一个目标值不负责处理第一个或最后一个位置那是34题的事。3.2 左闭右闭写法含C与Python实现左闭右闭的代码骨架如下我先给Python版本因为训练营打卡的同学很多用Pythonclass 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]所以left和right指向的元素都有可能是答案while条件必须允许left等于right的最后一轮检查。当nums[mid] target时mid及其左侧所有元素都小于目标新的搜索范围从mid 1开始当nums[mid] target时mid及其右侧所有元素都大于目标新的搜索范围到mid - 1结束。每一步都保证区间严格缩小循环必终止。C版本换成数组和vector后逻辑完全一致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; } };我建议把两种语言版本都写一遍不是为了炫技而是通过对比加深对语法之外的理解。同一个逻辑在不同语言里落地能帮你把算法思想和语言特性解耦。3.3 左闭右开写法与与闭区间对比左闭右开写法的核心是让right只作为边界哨兵不参与实际搜索。初始化时right len(nums)while条件变成left right因为left等于right时就意味着搜索范围已空。代码如下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 mid而不是mid - 1因为mid这个位置虽然被排除了但它的下标并没有变成哨兵真正起作用的还是[left, mid)这个区间循环退出时不需要检查left是否等于len(nums)因为while条件已经保证left right。左闭右闭和左闭右开的取舍其实是个习惯问题。相比之下我遇到的初学者更容易写对左闭右闭因为它更贴近查找某个具体位置的直觉。但左闭右开在处理重复元素的边界问题时更自然后面做34题时你会感受到。3.4 时间复杂度和空间复杂度分析二分查找每轮排除一半范围最坏情况下需要log2(n)次比较所以时间复杂度是O(logn)。这里的对数底数不重要因为复杂度分析关心的是增长趋势。空间方面只用了常数个变量没有额外数组是O(1)。这也是二分查找在有序数据查找中如此强势的原因时间和空间都极其节俭。这里补充一点容易被忽视的细节如果你在循环里提前返回了target下标那么找到的最优时间复杂度是O(1)也就是第一次mid就命中找不到的最差情况是O(logn)。LeetCode通常只报告平均和最差的渐进复杂度所以统一写O(logn)即可。另外如果nums的长度不是2的幂log2(n)只是一个上界。比如n5log2(5)约等于2.32最坏情况下需要3次比较。手动模拟下一节的样例就能看到这个过程。3.5 用手动模拟验证代码正确性我强烈建议初学者在提交前手动模拟一遍哪怕只模拟一个样例。以nums [-1, 0, 3, 5, 9, 12]target 9为例左闭右闭写法的执行过程如下初始left 0, right 5mid 0 (5 - 0) / 2 2nums[2] 33 9所以left 3。第二轮left 3, right 5mid 3 (5 - 3) / 2 4nums[4] 9命中返回4。再模拟一个找不到的情况target 2。第一轮mid 2nums[2] 33 2所以right 1第二轮left 0, right 1mid 0nums[0] -1-1 2所以left 1第三轮left 1, right 1触发while条件是left rightmid 1nums[1] 00 2所以left 2第四轮检查left 2, right 1left right退出循环返回-1。这个手动过程看起来繁琐但走两遍就会对边界更新产生肌肉记忆。4. 实操中的常见问题与排查实录4.1 死循环的标准症状与消除方法第一个常见症状是程序运行超时点击运行后卡住不返回结果多半是死循环。我用一个例子说明假设某人在左闭右开写法里nums[mid] target时写了left mid那么当区间缩小到left 3, right 4时mid 3nums[3] targetleft更新为mid也就是3区间永远停在[3, 4)死循环。消除死循环的办法可以总结成一条铁律每一轮循环结束搜索区间必须严格小于上一轮。如果发现某条更新路径可能让left和right的值保持不变那这行代码一定有误。我在白板上排查的时候会刻意找区间无法缩小的分支。还有一个细节容易被忽略如果数组长度特别大比如10的9次方数量级mid (left right) / 2的溢出问题就会真实发生。我在本地测试时用过一个trick故意把left和right初始化为接近int最大值的数去验证溢出情况换了left (right - left) / 2的写法后结果稳定。4.2 边界写错的典型样例与断点分析边界写错的典型后果是返回下标不正确或直接数组越界。举一个真实案例原来的代码用的是左闭右开right初始化为len(nums)循环条件写成left right。这个组合会导致当left等于right时仍然进入循环而此时left可能已经等于数组长度取nums[mid]直接越界崩溃。排查方法很简单准备三个必测用例。目标在数组最左端比如target -1目标在数组最右端比如target 12目标不在数组中且值大于所有元素比如target 13。这三个用例分别能暴露左边界更新错误、右边界更新错误、循环终止条件错误。还有一类隐蔽错误发生在目标值比数组所有元素都小的时候。左闭右闭写法里left 0, right len(nums) - 1循环正常结束后返回-1没问题。但如果有人在循环里提前返回了-1而不是等到循环结束那么前几轮mid没命中就会直接返回-1后面的元素全被跳过。4.3 从704到后续变体题的延伸路径704解决之后训练营第二梯队的题目基本围绕二分查找的变体展开。35题搜索插入位置要求返回目标值应该插入的下标34题需要找到重复元素的第一个和最后一个位置69题是整数平方根本质上是在有序整数区间里二分查找367题是判断完全平方数其实是在1到num之间二分。这些题目共同的核心能力是基于分情况讨论修改返回条件。以34题为例找左边界时即使nums[mid] target也不能直接返回而要继续向左收缩区间记录当前位置找右边界时则相反。如果你把704的循环不变量吃透34题的思路就是在这个框架上增加两个指针变量。我整理过一个小表方便训练营同学对照复习题目关键差异需要掌握的额外技巧704 二分查找元素唯一找到即返回两种区间写法的切换35 搜索插入位置找不到时返回插入点需要理解left最终指向的位置含义34 查找元素范围元素可能重复左边界与右边界的两次二分69 x的平方根整数结果向下取整防止乘法溢出注意返回right367 有效的完全平方数判断是否存在整数解同上注意边界收敛4.4 训练营第一天的复盘记录第一天打卡的常规流程是先看代码随想录对应章节再自己写题解最后提交AC并写总结。我在写总结时发现自己最初暴露的问题集中在区间定义不统一一会儿把right当闭区间用一会儿当开区间用导致更新逻辑混乱。复盘之后我给自己定了一个小规矩写题前先在注释里写清楚区间是左闭右闭还是左闭右开写完代码后随手在草稿纸上画出区间变化图。大约是坚持到第十题的时候这个习惯开始变得自然后面做35题和34题时明显顺手了很多。还有一个值得分享的点是一开始不要追求一行代码写完二分查找。训练营的目的是建立肌肉记忆不是炫技。我在网上看过不少一行二分的写法看起来厉害但初学阶段很难保证边界正确性不如老老实实写成三四行if-else分支稳定大于简洁。我自己的体会是刷算法题最忌讳似懂非懂就往下冲。704这道题虽然简单但它是你整个二分查找体系的奠基石。花一个小时把它的两种写法、三种测试用例、一种手动模拟全部折腾明白后面再碰到二分相关题目你心里就有底了。训练营第一天真正要完成的不是一道AC而是把区间即边界这四个字刻进习惯里。