1. 为什么“代码随想录训练营第一天”偏偏是二分查找如果你也报了“代码随想录算法训练营”或者正照着那份广为流传的刷题计划在走第一天打卡的题目大概率是LeetCode 704. 二分查找。很多朋友看到这道题的第一反应是“这不就是写个while循环吗”然后半小时过去要么死循环、要么边界错乱最后羞耻地点开题解——发现自己的问题出在没想清楚区间的开闭。从训练营的课程设计来看把二分查找放在第一天不是随意安排的。它是一个“看着简单、写对很难”的经典代表代码量不超过二十行但涉及的核心思想——区间不变量、循环终止条件、边界收缩——几乎贯穿后续所有数组、链表、二叉树乃至更复杂的算法题。能在第一天把二分查找的边界逻辑吃透后面写快排、红黑树、查找类的题都会顺很多这个铺垫价值往往被人低估了。这篇博文我会把这题的解题思路、代码写法、易错点全部拆开讲清楚。不管你是零基础刚开始刷题的新手还是已经刷过一些题但边界问题一直模棱两可的选手都可以对照着自查一遍。另外我还会把训练营里常见的打卡困惑——比如“为什么我的代码在目标值不存在时返回了奇怪的结果”——一起梳理出来避免你在同一个坑里反复栽跟头。2. 二分查找到底在考什么三个核心考点拆解2.1 考点一数组的有序性假设为什么是前提二分查找的前提是数组有序这一点很多人在做题时知道但实际写代码时却容易忽略。704题明确给出了“升序排列的整数数组”所以直接用二分没有任何问题。但面试或者实际项目中数据往往不会天然有序这时候不能用二分硬套而是要先用排序把它变成有序的或者换用哈希表等结构来解决查询问题。这里我想多说一句二分查找的核心逻辑是通过中间值和目标值的大小对比每次排除一半的搜索区间。如果数组无序中间值的大小关系就和左右两侧的分区没有必然联系你压根没法判断目标值到底在左边还是右边。这就像翻一本没有页码的字典随便翻一页看到个字你根本不知道它是在前面还是后面。所以在刷题的时候看到“有序数组”四个字条件反射地想到二分是好事但同时也别急着写代码。先问自己一句这个有序性在整个计算过程中会不会被破坏比如有没有在循环里做旋转、插入、删除之类的操作确认没有再开始写二分。2.2 考点二区间的开闭直接影响整段代码二分查找最阴险的地方就是区间的开闭。同样的思路你可以写左闭右闭[left, right]也可以写左闭右开[left, right)两种写法都能通过但while条件、middle的更新方式、初始值全都不一样。704这个题我用的是左闭右闭。具体来说left初始化为0right初始化为nums.length - 1。注意这里的right不是nums.length而是数组最后一个元素的下标因为闭区间里right本身是“能被取到”的。这样一来while循环的条件是left right为什么能取等号因为当left right时区间里恰好还剩一个元素这个元素也得判断一下才能下结论。换个角度看左闭右开left还是0right初始化为nums.length。因为nums.length这个位置是不存在的它代表的含义是“区间终点不包含”。这种情况下while条件就只能是left right因为一旦left right区间已经是空的了再循环就多余了。这两种写法没有绝对的好坏但我建议大家在初学阶段先认死一种左闭右闭。理由很简单它更符合人类的直觉——搜索的区间从下标0开始到最后一个下标结束都是合法的位置。你在推边界的时候不容易把自己绕晕。等熟练了再拿左闭右开练手对比两种写法的差异这会让你对二分的理解上一个台阶。2.3 考点三while循环为什么不退出就成了死循环训练营里很多同学反馈的典型问题是代码看着没问题但一运行就超时基本可以判定是死循环。死循环的根源往往是middle的计算和边界更新没有导致区间“严格收缩”。核心原则就一句话每一轮循环之后搜索区间必须严格缩小否则就是死循环。具体到代码里当nums[middle] target时说明目标值在右半边left应该变成middle 1而不是middle。为什么不能是middle因为nums[middle]已经明确小于target了这个位置已经检查过了再把它留在区间里下一轮还会再检查一次如果恰好middle更新方式有问题区间就可能一直不变。同理当nums[middle] target时right应该变成middle - 1。注意这里是middle减1不是middle。很多人在这个地方出错觉得“middle既然比target大那target应该在左边区间右边界收敛到middle不就行了吗”不行因为middle位置的值已经被检查过并且排除掉了左闭右闭区间里right必须跳过一个已排除的位置。另外middle的计算看似无关紧要但这里有经典一坑直接用(left right) / 2在极端情况下可能溢出。left和right都接近int最大值的时候两者相加超过int上限结果就变成负数了。标准写法是left (right - left) / 2数学上等价于(left right) / 2但避免了溢出。这个细节刷题阶段可能感知不到但在数据量大的工程场景下是实打实的bug。3. 704题从思路到落地完整代码与逐行拆解3.1 完整可运行的题解左闭右闭方式)先贴出我在训练营里提交并通过的完整代码语言用的是Java思路其他语言完全通用class Solution { public int search(int[] nums, int target) { // 左闭右闭区间left和right都是合法的数组下标 int left 0; int right nums.length - 1; // 当left right时区间内至少还有一个元素需要判断 while (left right) { // 防止溢出的中间值计算方式 int middle left (right - left) / 2; if (nums[middle] target) { return middle; } else if (nums[middle] target) { // 目标值在右半边排除middle及左侧所有元素 left middle 1; } else { // 目标值在左半边排除middle及右侧所有元素 right middle - 1; } } // 循环结束说明区间为空目标值不存在 return -1; } }如果你用的是C把数组访问和变量声明稍微改一下就行。Python的话更简单整个函数体几乎可以原样平移只是把int声明去掉、用Python的除法注意一下取整即可。class Solution: def search(self, nums: List[int], target: int) - int: left, right 0, len(nums) - 1 while left right: middle left (right - left) // 2 if nums[middle] target: return middle elif nums[middle] target: left middle 1 else: right middle - 1 return -13.2 用实际例子推演一遍执行过程光看代码不推演很容易觉得自己懂了其实没懂。我们拿题目的示例来跑一遍nums [-1,0,3,5,9,12]target 9。初始化left 0right 5middle 0 (5 - 0) / 2 2nums[2] 3。第一轮判断3 9说明目标值在右半边left变成3right还是5。此时搜索区间从[0,5]缩小为[3,5]检查过的下标0、1、2全部排除注意这里的3其实就是之前middle的下标加1。第二轮middle 3 (5 - 3) / 2 4nums[4] 9恰好等于target直接返回4。如果target换成2呢nums [-1,0,3,5,9,12]target 2。第一轮middle 2nums[2]33 2说明目标值在左半边right变成1。此时left0right1区间里还剩下标0和1。第二轮middle 0 (1 - 0) / 2 0nums[0] -1-1 2left变成1。此时left1right1区间还剩一个元素也就是下标1。第三轮middle 1 (1 - 1) / 2 1nums[1]00 2left变成2。此时left2right1left right循环退出返回-1。这个推演过程建议你自己在纸上完整走一遍尤其是left和right收敛到相等时为什么还要再判断一次。训练营里很多人栽在“明明区间里只剩一个元素了为什么还要循环”这个问题上——因为那个唯一的元素还没有和target比较过是你最后的查找机会。3.3 数组为空和长度为1的边界情况边界情况是二分最容易翻车的地方建议拿到任何一道二分题先想这三个场景数组为空、数组只有一个元素、目标值在数组第一个位置、目标值在数组最后一个位置。数组为空的情况nums.length 0那么right初始化为-1left0left rightwhile条件不满足直接返回-1。代码天然处理了这个边界不需要额外加if判断但你要能看懂为什么不会报错。数组长度为1nums [5]target 5。left0right0middle0nums[0] target返回0。如果target 3left0right0middle0nums[0]5 3right变成-1循环退出返回-1。这两种情况推一遍左闭右闭的代码逻辑就完全清晰了。很多人写二分第一版代码往往通不过上述场景。比如有人在while条件里写left right数组只有一个元素的时候循环根本进不去返回-1但目标值明明就在里面。这就是区间定义和while条件不匹配导致的bug。4. 训练营打卡实录我踩过的和看到别人踩过的坑4.1 经典返场问题不同写法混搭导致边界错乱这篇文章先在训练营内部流传的时候有同学问我“我用左闭右闭的思路初始化但while里写的是left right然后AC了是不是也行”这种情况其实分两种如果区间初始化为左闭右开right nums.length那left right是对的如果初始化是左闭右闭right nums.length - 1那left right就会漏掉“区间里只剩一个元素”的最后判断。但这位同学说自己的代码AC了那是怎么回事我让他把代码发出来发现他while里是left right但return前又写了一句“if (nums[left] target) return left;”。这不叫逻辑自洽这是拿特判补救边界的错误。如果你的二分代码里出现了类似“循环结束后再单独判断一下”的补救代码大概率是边界条件没有想透。我理解训练营打卡时有通过率焦虑但既然花了时间做这道题建议还是把逻辑调成自洽的状态而不是靠补丁通过测试。否则下次面试面试官随便改改输入数据你的“特判代码”就露馅了。4.2 死循环排查的实操手段遇到超时第一反应不应该是“我的代码太慢”而是“我的循环没退出来”。我在实际排查中会做两件事第一在循环里打印left、right、middle三个变量的值看在某一次迭代中这三个值是不是保持不变。如果连续多次三个值一模一样说明middle没有让区间收缩基本可以定位到left或right的更新写错了。第二手动推演“区间只有两个元素”的情况。比如left1right2middle计算出来必然是1。这时候如果nums[middle] targetleft应该变成middle 1也就是2区间变为[2,2]下一步还可能继续。如果代码里写的是left middle那区间就还是[1,2]下一次middle还是1就死循环了。死循环的本质原因我前面讲过就是区间没有严格缩小。这里再补充一个类比你玩过找东西的游戏吗每当你说“大了”或“小了”对方会把可能范围缩小一半。但如果你说完“大了”之后还是把刚才那个位置保留在范围内下一轮你会重复检查同一个位置永远找不到目标。二分的边界更新本质上就是在说“这个位置我已经看过了扔掉它”。4.3 目标值不存在时的返回值误区704题要求目标值不存在时返回-1这道题简单直接-1就行。但训练营后续会学到搜索插入位置35题、搜索旋转排序数组33题这类变体到时候你会遇到“返回第一个大于target的位置”或者“返回最接近target的位置”等需求。现在在704上把区间收缩的推演练熟到那些题里循环结束后的left或者right是有明确含义的不再是简单的-1。具体来说左闭右闭写法下循环结束时left指向第一个大于target的位置如果没有大于target的元素left会指向nums.lengthright指向最后一个小于target的位置。记住这个规律后面做“搜索插入位置”几乎可以直接抄答案。这也是为什么我强烈建议你认真对待704这道“简单题”的原因。它简单是因为它没有把边界情况变化成复杂的业务逻辑但它把所有二分的基础机制展示得非常干净。把这道题吃透等于给后续所有二分变种题打了个地基。5. 从704出发一次搞懂b站热词“二分查找pta函数”5.1 什么是PTA平台上的二分查找函数题有朋友近期在刷网的时候看到“二分查找pta函数”这个热词来问我这是不是另一个题。其实PTA是程序设计类实验辅助教学平台的缩写很多高校的C/C课程作业都会布置这道题本题要求实现二分查找函数函数接口定义通常是int Search(int a[], int n, int key);这个函数的功能是在长度为n的有序数组a中查找key找到了返回下标找不到返回-1。本质上和LeetCode 704是同一个东西区别在于PTA一般要求你只实现函数体不关心main函数里的输入输出格式。我提这个是因为训练营里不少学生同时在校内课程和LeetCode刷题会混淆两边的题面要求。其实算法核心完全一致你只要能把704写清楚PTA这道题基本就是改一改函数签名的事。5.2 PTA版本和LeetCode版本的三处差异差异主要在代码组织形式上不在算法上。实际做题时注意这三个点就够了第一函数命名和参数列表必须按题面要求写。PTA往往对函数名有硬性要求比如就叫Search你写成binarySearch直接编译错误。第二PTA题大多数用C语言数组作为参数传递时退化为指针所以a.length这种操作不存在你必须接收一个额外的数组长度参数n。第三PTA判分时可能隐藏测试数据用了超大数组这时候“middle (left right) / 2”就可能在极端情况下溢出。虽然PTA后台未必真的构造了那么极端的int最大值输入但养成用left (right - left) / 2的习惯永远不会亏。我把两边对应的注意点放在一起做个对比表方便你打卡的时候对照对比维度LeetCode 704PTA二分查找函数题提交内容完整类或完整函数通常只写函数体函数名searchJava/Python等SearchC语言常见命名数组长度通过nums.length获取通过参数n传入返回值要求找不到返回-1同样找不到返回-1判分方式多种编程语言均可按课程要求C/C居多5.3 热词“二分查找”延伸出来的高频变体“二分查找”作为网络热词搜索关联里往往还会冒出“二分查找的递归写法”“二分查找的mid计算为什么不能写(rightleft)/2”这类问题。我在这里一并说一下。递归写法本质就是“把while循环换成递归调用”每次递归把新的left和right传下去终止条件是left right。我个人在刷题阶段更推荐先写熟迭代版本因为递归版本每层调用都有函数栈开销虽然刷题时性能差别不明显但面试白板写迭代更稳也更容易解释清楚。至于mid的计算网上讨论已经很多了。用(right left) / 2的问题在于溢出这在32位int的情况下是真实存在的。我在训练营的实践里也反复强调过不要觉得这是一个“理论风险”你把它当成固定习惯写进肌肉记忆就行反正在可读性上没有差别。6. 训练营之外的自我要求怎么练才算真正掌握了二分6.1 一个检验方法十分钟手写三种变体训练营第一天的内容虽然只有704一道题但我给自己定的检验标准是一口气写出三份代码迭代版二分、递归版二分、递归版二分查找第一个大于等于target的位置。十分钟内写完且不用看题解才算真正过了二分这一关。第一个是704原题你正常练习会写。第二个递归版主要是让你更清晰地理解区间的递归收缩过程。第三个是为后续“搜索插入位置”做铺垫锻炼的是“在循环结束后利用left/right含义而不是单纯返回-1”的能力。我在训练营内也推荐过这个自测方法。如果第三份代码写不出来不用焦虑它本来就是扣着“35. 搜索插入位置”这题设计的你可以在完成当天的704打卡后第二天再做35题然后回头用这个标准检验第一天的学习效果。6.2 配套练习建议与顺序推荐训练营计划本身是循序渐进的但如果你想做一点额外巩固我建议按这个顺序704. 二分查找 - 35. 搜索插入位置 - 34. 在排序数组中查找元素的第一个和最后一个位置 - 69. x 的平方根 - 367. 有效的完全平方数。这几道题的递进关系很清晰704是基础查找逻辑35开始利用循环结束时left/right的位置信息34把二分拆成两次查找69和367则是把二分从“数组索引”扩展到“数值区间”。做完这一串你对二分的理解就不再局限于“在数组里找一个数”而是懂得在一个单调空间里寻找分界点的通用方法。我为什么推荐这样的递进而不建议直接去刷旋转数组之类的高阶变形因为旋转数组需要额外的条件判断容易把初学者的注意力从“区间不变量”带到“怎么判断哪半边有序”上去。先把简单的、顺序数组上的二分写稳再挑战旋转数组心理上更从容逻辑上也更有抓手。6.3 每天都在做二分题为什么会越刷越糊涂训练营里有同学问我一个很真实的问题“老师我天天都在做二分但每次新题还是不知道怎么下手是不是我太笨了”其实这不是笨而是陷入了“题海战术但缺少复盘”的陷阱。二分的坑点不在“会不会写while循环”而在于“能不能在开写之前定义清楚自己的区间模型”。我每次做题都会在注释里先写一行// 左闭右闭left和right均合法。然后所有代码逻辑都围绕这一行来写。这么做的原因是给自己立一个“不变量”后续任何一步判断都和这个模型保持一致不容易前后矛盾。建议你也尝试这种方式哪怕慢一点哪怕一开始写代码前要想两分钟也值得。等到你形成了固定的模型再看二分的变种题思路的起点就不一样了你不是在“套模板”而是在“沿用一套自洽的规则”。这也是我在训练营里反复推崇的“用不变量统领代码”的刷题方法——它适用面远不止二分链表操作里也很常用。7. 最后再分享一点我的实际操作体会训练营第一天的题目我刷了三遍才算心里有底。第一遍是看题直接写写出了个能AC但自己都讲不清楚right为什么是middle-1的版本。第二遍是刻意用左闭右开重新写对照左闭右闭的代码总算彻底理解了区间开闭对整个代码结构的影响。第三遍是做35题搜索插入位置的时候发现不靠特判也能直接利用循环结束后的left返回值那一刻才觉得704真正吃透了。所以如果你今天卡在某个边界上不用着急甚至可以故意用两种区间定义各写一遍对比着看差异。这个过程比AC十道题还有用。二分查找是一个值得花一整天来磨的算法它会在你后续刷题生涯里反复出现与其囫囵吞枣地跳过不如在最开始就把地基打扎实。