今天是代码随想录算法训练营的第一天内容锁定在二分查找和双指针。说实话这两个名字听起来都挺基础但训练营里第一天就卡壳的人不在少数——不是题目看不懂而是自己写的二分查找在几个边界用例上反复出错或者双指针的思路一听就懂、一写就废。如果你正处于看得懂题解、写不出能跑的代码的状态这篇文章就是给你准备的。我会把二分查找的边界本质、双指针的三种套路、每个模板背后的设计理由以及第一天的刷题节奏全部拆开讲清楚让你今天学完就能直接拿去用。1. 二分查找的第一道坎区间边界为什么总在搞事情1.1 先想清楚 left 和 right 到底是什么意思很多人写二分查找背的是模板但没想明白模板为什么长这样。一旦题目变个花样比如找不到target时返回插入位置、或者数组里有重复元素要返回最左/最右边界模板就失灵了。问题的根源在于你没有定义清楚区间不变式。所谓区间不变式就是你在整个查找过程中始终坚持的一个约定。最常见的约定有两种左闭右闭[left, right]表示当前查找范围包含 left 和 right 两个位置。左闭右开[left, right)表示当前查找范围包含 left但不包含 rightright 只是一个哨兵边界。这两种约定没有绝对的好坏但你必须从头到尾遵守同一个。最经典的翻车现场是把两种写法混在一起用循环条件用的是left right开区间习惯收缩右边界时却写right mid - 1闭区间习惯结果在某些用例下跳过目标元素或者直接死循环。我用的是左闭右闭这套约定因为它在理解上最直白既然 right 是真实存在的下标那么当nums[mid] target时mid 及其右边所有元素都不可能再有目标值所以right mid - 1当nums[mid] target时mid 及其左边全部排除所以left mid 1。循环继续的条件是left right因为当 left 和 right 重叠时这个位置还没有被检查过。先看标准模板C 写法如下int binarySearch(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; }Python 版本同理def binary_search(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收缩右边界时必须写right mid因为 right 本身不参与检查把它移到 mid 位置就相当于把 mid 排除掉了。两种约定都能正确工作怕就怕今天写一种、明天写另一种大脑来不及切换错题率飙升。1.2 防死循环与 mid 计算的三个细节细节一mid 为什么是left (right - left) / 2而不是(left right) / 2在 C 或 Java 这类语言里如果 left 和 right 都是接近 2^31 - 1 的大整数直接求和left right可能直接溢出成负数mid 变成负值数组越界访问程序崩溃。left (right - left) / 2先算差值再除以 2从数学上避免了大数相加的溢出风险。Python 的 int 没有溢出问题但写成这种形式也能让代码在语言之间迁移时不踩坑。细节二为什么收缩边界是mid 1或mid - 1而不是mid这要回到不变式。我们已经确认nums[mid]不是目标值它是一个已经检查过的位置那就必须把它从下一轮搜索区间里剔除。如果写成left mid那么当区间缩小到只剩两个相邻元素时mid可能一直是 left 本身left 永远不前进循环出不来这就是死循环的典型成因。细节三什么时候用left right什么时候用left right这取决于你的区间约定。左闭右闭下当left right时区间内还有一个元素需要检查所以必须继续循环条件是左闭右开下当left right时区间已经为空循环条件就是。判断依据不是背下来而是问自己当前这个区间里还有没有未检查的元素有就继续没有就退出。我第一天自测时故意用了一组特殊情况数组[5]查找5。如果你用左闭右开却写right mid会发现在长度为 1 的数组里这组代码也能跑对但换到[1, 5]查5就可能出错。所以强烈建议第一天就把两种约定各写一遍并且用[1]、[1, 3]、[1, 3, 5, 7, 9]这类小数组手推几轮把每一步的 left、right、mid 变化写在纸上。这个习惯比多做十道题都管用。2. 从查找一个值到查找一个边界二分模板的进阶用法2.1 有重复元素时怎么找左右边界LeetCode 34 题是二分查找的经典进阶题给定一个按非递减顺序排列的数组要求找出目标值的第一个位置和最后一个位置。很多人拿到这题的第一反应是先二分找到任意一个 target然后往前往后线性扩散。这在数组元素全是同一个值的极端情况下会退化到 O(n)白白丢掉二分查找的 O(log n) 优势。正确做法是写两个变体模板一个找左边界一个找右边界。左边界模板的关键变化是当nums[mid] target时不着急返回而是把右边界继续往左收尝试寻找更靠前的目标值。用左闭右开区间写起来最干净int leftBound(vectorint nums, int target) { int left 0, right nums.size(); while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { left mid 1; } else { right mid; } } return left; // left 就是第一个 target 的位置 }这里把nums[mid] target和nums[mid] target合并成了同一个分支都执行right mid意思是就算找到了左边界也有可能藏在更左边。最后返回的 left 指向第一个不小于 target 的位置。如果题目要求返回下标且 target 必须存在需要额外判断nums[left] target。右边界模板是对称的当nums[mid] target时把左边界往右收寻找更靠后的目标值。int rightBound(vectorint nums, int target) { int left 0, right nums.size(); while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { right mid; } else { left mid 1; } } return left - 1; // left 是第一个 target 的位置减 1 就是最后一个 target }这两个模板看起来只是把等号换了个分支实际反映了一个关键思维转变二分不只可以查值还可以查位置边界。理解这一点35 题搜索插入位置也就顺手解决了——插入位置本质上就是左边界模板的返回值。2.2 当数组不存在时答案二分的思想还有一种更隐蔽的二分应用叫答案二分。它不直接在一个数组里查找而是在一个单调的值域范围里查找答案。典型题目就是 69 题 x 的平方根。你可能觉得平方根直接调库函数就行但题目要求实现 int 范围内的整数平方根不能用浮点库函数。这时候观察到一个关键性质整数 x 的平方根一定落在[0, x]这个区间里并且mid * mid x这个条件在整个区间上呈前一段为真、后一段为假的单调分布。二分就是用来找最后一个满足条件的 mid的。int mySqrt(int x) { int left 0, right x; while (left right) { int mid left (right - left) / 2; if ((long long)mid * mid x) { left mid 1; } else { right mid - 1; } } return right; }注意这里有个小坑mid * mid可能溢出 int所以要么转成 long long要么写成mid x / mid的除法形式。这个细节我不止一次看别人在面试时现场踩中。答案二分的思想不仅限于平方根还能延伸到在一个值域里找满足某种单调性质的最小值/最大值这类问题比如寻找满足条件的最小速度、最小电量等。它和数组二分的本质其实一模一样只要你能构造出一个单调的判定函数就可以用二分把这个阈值找出来。训练营第一天能把这个思路建立起来后面做那些最大化最小值的难题会顺畅很多。3. 双指针的三种套路快慢、对撞和链表追逐3.1 为什么双指针能把 O(n²) 变成 O(n)如果二分查找的关键词是单调那双指针的关键词就是分工。很多暴力解法之所以慢是因为同一个指针既负责遍历、又负责记录结果导致你不得不在循环里套循环。双指针的核心思想很简单把一个指针承担的两种职责拆给两个指针去干一个负责探测快指针一个负责写结果慢指针指针之间通过信息差来协作整体只遍历一遍时间复杂度从 O(n²) 降到 O(n)。我第一天学双指针时老师给了一个特别直观的比喻快指针像在前面探路的侦察兵负责往前看每个位置的值是不是目标值慢指针像跟在后面收拾战场的工程兵只负责把有用的东西放到该放的位置。两个人各干各的互不干扰一趟走完所有没用的元素都被甩在了身后。3.2 同向快慢指针移除元素与去重LeetCode 27 题移除元素是同向快慢指针最经典的入门题原地删除数组中所有等于 val 的元素返回新数组长度。我第一次做这题时用了最笨的办法——找到 val 就调用 erase 删掉。表面看起来没错但vector的 erase 会触发后面所有元素的搬移最坏情况下删除 n/2 个元素每次搬移 O(n)总复杂度 O(n²)。在 LeetCode 上虽然数据量小能过但这绝不是训练营想让你掌握的解法。快慢指针写法如下int removeElement(vectorint nums, int val) { int slow 0; for (int fast 0; fast nums.size(); fast) { if (nums[fast] ! val) { nums[slow] nums[fast]; } } return slow; }fast 负责遍历数组slow 始终指向下一个要填入的位置。当 fast 发现一个不等于 val 的元素就把它放到 slow 指向的位置然后 slow 前进一步。等于 val 的元素直接跳过slow 位置上的值在后续遍历中会被覆盖掉相当于原地逻辑删除。这个模板一通百通。26 题删除有序数组中的重复项只是把判断条件从nums[fast] ! val改成nums[fast] ! nums[fast - 1]代码结构几乎不动283 题移动零则是把非零元素按顺序放到前面剩下的位置补零本质上仍是快慢指针。我建议你把这三道题放在一起刷刷完之后做一个小总结它们的共同点是快指针负责遍历慢指针负责维护结果区间的末端不同点只是筛选条件。总结出了这个共性你才算真学会了这个套路而不是记住了三道题的代码。3.3 左右对撞指针有序数组与反转问题第二种套路的两个指针不在同一侧起步而是一个从最左边、一个从最右边向中间逼近。最典型的应用是有序数组的两数之和找两个数使它们的和等于 target。暴力的 O(n²) 解法是双重循环对撞指针的做法是left 指向数组头、right 指向数组尾计算sum nums[left] nums[right]。如果 sum 太大说明右边的数太大right--如果 sum 太小说明左边的数太小left相等就找到了答案。整个过程两个指针各扫一遍O(n) 解决。有序数组的平方977 题也是同一个思路的变体平方后的最大值只可能出现在数组两端不可能出现在中间。所以用 left、right 分别指向原数组两端比较平方大小把较大的平方放到结果数组的末尾从后往前填充。vectorint sortedSquares(vectorint nums) { int n nums.size(); vectorint res(n); int left 0, right n - 1, pos n - 1; while (left right) { int l2 nums[left] * nums[left]; int r2 nums[right] * nums[right]; if (l2 r2) { res[pos--] l2; left; } else { res[pos--] r2; right--; } } return res; }这个写法还有一个好处是结果天然有序不需要最后再 sort 一次。3.4 链表里的快慢指针判环与找中点第三种套路发生在链表场景。经典的快慢指针判环问题中慢指针每次走一步、快指针每次走两步。如果链表中有环快指针终会在环里追上慢指针这就好比两个人在环形跑道上跑步速度快的人迟早会从后面套圈追上速度慢的人如果没有环快指针会先一步抵达链表末尾的空指针。bool hasCycle(ListNode *head) { ListNode *slow head, *fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) return true; } return false; }同样的快慢指针还可以用来找链表中点快指针到终点时慢指针恰好走到一半。这个技巧在很多链表类题目里是前置步骤比如排序链表要求先找到中点再分治训练营后面的递归、链表综合题里会频繁用上。第一天先把这种跑得快和跑得慢的信息差模型建立起来后面见到就不会再觉得难。4. 第一天的实战节奏题目清单、复盘方法和新手常见误区4.1 按这个顺序刷题难度曲线最平滑训练营第一天不建议贪多也不需要把二分和双指针的所有变体全都做完。下面这张清单是我带过几轮学员后觉得比较顺手的顺序每道题都踩在前一道的基础上难度逐步抬升。题号题目核心考点建议时间704二分查找基础二分模板15分钟35搜索插入位置二分的返回值处理15分钟34在排序数组中查找元素的第一个和最后一个位置左右边界模板25分钟69x 的平方根答案二分思想15分钟367有效的完全平方数二分判断边界10分钟27移除元素快慢指针基础10分钟26删除有序数组中的重复项快慢指针变体10分钟283移动零快慢指针再变体10分钟844比较含退格的字符串双指针反向遍历20分钟977有序数组的平方对撞指针10分钟如果你时间有限704、34、27、977 四道务必先吃透它们是训练营后续所有题目里最容易复用的模板来源。844 这道题可以留作当天的思维拓展双指针从同向移动变成从末尾向开头移动能帮助你在第一天就建立指针移动方向不唯一的意识。刷题时还必须养成一个习惯每道题 AC 之后用一两句话写下它用的是什么模板、和上一题的区别在哪。比如 26 题就是27 题的判断条件换成相邻去重34 题就是704 的等号分支拆开成两个模板。这比收藏十个题解都更有价值因为你在逼自己把题目归类而不是孤立地记代码。4.2 遇到卡壳时按这个排查链路走训练营第一天大概有九成的人会在以下三种情况里至少栽一次。我把自己教过学员的实际报错情况整理成一条排查链路按顺序检查绝大多数问题都能自己定位。死循环或超时先检查循环条件。左闭右闭却写left right会在区间只剩一个元素时提前退出左闭右开却写left right会多一轮循环导致下标越界。修复原则是回到你定义的区间不变式重新确认 left、right 表达的含义。答案差一位比如返回 -1 但目标明明存在检查 mid 的收缩方向。nums[mid] target时 left 是否写成了mid而不是mid 1nums[mid] target时 right 是否多减了 1这类问题的典型特征是只在特定长度的数组上出错因为边界只在临界位置暴露。结果正确但返回的下标位置偏了检查你最终返回的是 left、right 还是 left - 1、right 1。找右边界时常见错误是返回left而不是left - 1因为前面的模板里 left 会停在第一个大于 target的位置目标要往左挪一格。每次卡壳先在本地把[1, 3, 5, 7]这类小数组手动推一遍把每一步 left、right、mid 打在控制台里看不要直接去看题解。训练营第一天最重要的不是刷题数量而是学会这套自己找 bug的排查能力。你如果在第一天就掌握了这个思路后面两个月会省下大量刷题时间。4.3 给新手的心理建设第一天不需要全懂我见过很多同学第一天结束就很沮丧原因是 34 题的左右边界模板看懂了但自己默写时又写错844 题想了二十分钟没思路看到评论区有人一天刷了十题心态直接崩掉。这一般是很多训练营学员第一天就放弃的直接原因。说实话第一天的内容放在整个算法体系里已经超过了很多人的舒适区。左右边界模板本质上是二分答案的雏形答案二分思想又是一块独立的思维方式指望一天内从零基础到完全掌握既不现实也没必要。我的建议是第一天把 704、27、977 这三道题做到不看参考能独立写对其余题目哪怕只理解了思路、没写对代码都可以接受。34 题和 69 题在训练营后面还会反复出现到时候再巩固就行。另外一个很实际的心理技巧控制单题时间。一道题如果想了 30 分钟还没有任何思路果断看题解看懂之后合上书自己从头写一遍。这一步非常重要——看懂的懂是假懂合上书能写出来的懂才是真懂。第一天至少留出 1 小时给关书写题环节比多刷两道新题有用得多。最后分享一个我的懒人习惯第一天学完我会把两种二分模板和一个快慢指针框架抄在一张便利贴上贴在显示器下沿。之后一周内每次写错边界就回去对着便利贴改一边改一边回想当时卡住的原因。三天之后错误就明显少了一周之后基本不需要再看便利贴——因为那些坑已经长在肌肉记忆里了。你也可以试试这比任何花里胡哨的方法论都实在。