这个系列课程走到第六节Class 06 的主题是搜索。说句实话听到这个题目的时候我一开始是有点松弛的——搜索谁不会写无非就是一个循环加一个判断条件成立就返回。可真等我把课后题刷完、又和几个学员对了答案之后才发现越是基础的概念越容易在细节上翻车二分模板看着短边界一改就死循环DFS 和 BFS 都能过样例数据规模一大会一个爆栈一个超时。这一篇我就把第六讲的完整梳理写下来从搜索到底在搜什么开始过一遍二分、DFS、BFS再进阶到剪枝和双向 BFS最后收在几个实战里最常见的坑上。如果你是刚开始学数据结构的新手或者正在补算法短板的开发者这份笔记应该都能用得上。1. 搜索课的关键认知搜索是空间缩减不是遍历1.1 用猜数字游戏理解搜索空间第六讲的第一课讲师反着来先让大家玩了一个猜数字游戏系统在 1 到 100 里随机一个数你每次猜一个数系统只告诉你是大了还是小了。很多人下意识从 1 开始往上试运气好一次能中运气差要猜几十次。后来有人说应该每次都猜中间因为每一次反馈都能把候选范围砍掉一半最坏情况也只需要 7 次。这个游戏看起来简单但它是理解搜索最好的入口。1 到 100 的整数是搜索空间每一次猜测是一次决策系统给的反馈把搜索空间进一步压缩。重要的不是猜了几次而是每次获得信息之后你是否真正利用了这条信息去缩小下一轮的范围。代码里的搜索也一样哪怕你不套任何现成算法只要每轮都能排除掉不可能的区域循环次数就会从线性变成对数级。这个例子也解释了为什么很多人写搜索时总差一口气他们不是在缩小空间是在盲目遍历。遍历是对每个候选都检查一遍搜索则是不断用条件砍掉不可能是答案的部分。认知上转不过这个弯后面的二分和剪枝都会学得很别扭。1.2 搜索问题的三要素状态、目标和策略走到第六讲对搜索的认知会升级成一套通用的元模型。任何搜索问题都能拆成三样东西状态、目标、策略。状态是当前所处的问题位置猜数字里的状态是候选区间 [1,100]走迷宫里的状态是当前格子坐标目标是要找的东西可能是特定数值可能是终点格子也可能是一组满足约束的解策略则是下一步要不要走、往哪里走的规则。为什么要做这个抽象因为一旦意识到搜索在状态空间里找目标状态你会发现很多过去以为不相关的问题本质上是同一个东西。排序里的查找、数据库里的索引命中、走迷宫、解数独、规划路径都属于搜索问题只是状态的定义各不相同。二分里的状态是一段区间DFS 里的状态是当前路径和剩余可选集合BFS 里的状态是某一层的节点。这一讲真正要训练的能力不是背下几个算法而是拿到一道题能迅速说出我的状态是什么、目标是什么、扩展策略是什么。这个抽象还带来一个额外好处你可以在不同算法之间做迁移。只要你把状态定义好了DFS 和 BFS 的模板可以直接套用区别只是用什么数据结构去维护待扩展状态而已。1.3 为什么有序是搜索中最值钱的线索搜索性能的天花板往往取决于你能不能借到数据结构里的序。同样是一堆数在乱序数组里找一个值只能线性扫最坏情况要扫到最后一个但给一个有序数组一百万个数里定位目标二十次比较以内一定能出结果。不过这里要强调一个容易误会的地方有序并不是唯一可用的线索。无序数组可以用哈希表把查找变成 O(1)树形结构可以靠二叉搜索树的路径逼近图可以靠拓扑序或层级关系去约束方向。所谓高级搜索算法本质就是通过数据里天然存在或人为维护的秩序来减少探索量。所以课上会反复问一个问题给你一组数据你能指出它身上有哪些序可以借从这个角度挖线索搜索题基本就成功了一半。这也是为什么第六讲会把二分放在第一个讲。二分是利用有序性最直接、最精巧的例子理解它之后再看到跳跃表、线段树、单调栈这类数据结构时你会有种熟悉感它们都在维护某种序让搜索路径缩短。2. 二分搜索模板只有三行边界却值一整节课2.1 while 条件与 mid 取整的两种搭配二分模板网上到处都是可真到手写环节死循环依然是出现频率最高的问题。我讲二分习惯让学员先把一套固定的左闭右闭模板焊死在脑子里def binary_search(nums, target): left, right 0, len(nums) - 1 while left right: mid (left right) // 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 重合时这个位置本身还没被检查过必须再进一次循环。如果你把 while 写成left rightleft 等于 right 时循环直接退出那个位置就会被漏掉。mid 的取整用的是向下取整。在左闭右闭区间里这么取没问题可一旦目标变成了搜索右边界mid 的取整方向就得认真考虑。很多死循环的根源都是把不同模板的片段混着用用左闭右开的 while 条件配左闭右闭的 mid 更新最后 left 和 right 卡在相邻位置永远动不了。2.2 左右边界查找的两类变体怎么写工程里更多时候我们搜的不是目标是否存在而是第一个大于等于 target 的位置或最后一个小于等于 target 的位置。比如订单列表里找第一个满足时间条件的记录这种边界查找在生产代码里非常常见。求左边界第一个大于等于 target 的位置def lower_bound(nums, target): left, right 0, len(nums) while left right: mid (left right) // 2 if nums[mid] target: right mid else: left mid 1 return left这版用的是左闭右开区间[left, right)。right 的初始值是len(nums)而不是len(nums) - 1意味着 right 这个索引本身不参与检查。循环里如果nums[mid] targetmid 可能是答案但左侧还可能有更小的满足位置所以把 right 缩到 mid否则说明 mid 位置太小left 果断跨到 mid 1。循环结束时 left 和 right 相遇位置就是左边界。记住一个判断技巧while 条件写成left right时结束于 left 与 right 相等此时返回 left 还是 right 都一样不用纠结。但你必须保证每次循环里 left 或 right 至少有一个真的在移动否则一进循环就出不来。2.3 二分不只看有序还要看单调一个常见的误区是数组有序就能二分。严格说二分能用的前提是左右两个方向上的性质具有单调性——也就是说存在一个分界点分界点一侧都满足条件另一侧都不满足。有序数组只是满足这个条件的一种情况。举个例子某天爬山的海拔变化不是整体单调的但如果你要找首次超过 3000 米的位置从山脚到山顶这段路程里是否超过 3000 米这个布尔属性是单调变化的之前全是 false之后全是 true。这就完全可以二分即使整个海拔序列本身不是单调递增的。实操里我建议用三个问题判断二分是否可行当前区间能不能用某个条件分成左右两半是否一边满足、另一边不满足满足条件与否的判断能不能 O(1) 完成三个答案都是肯定的就放心写二分哪怕原始数据并不是全局有序。第六讲后面所有进阶搜索题本质上都在帮你练这个本领构造那个可分两半的条件。3. DFS与BFS状态空间里的两种走法3.1 把全排列、组合、岛屿问题都归一到搜索视角第一次接触全排列问题很多人第一反应是套库函数或者写多层循环。可循环层数一多代码就失控了。第六讲里用状态搜索树把所有这类问题统一起来每个节点代表当前已经选了哪些数每条边代表下一步可以选哪个数。于是全排列、组合、子集、岛屿数量全都能画成这样的树或图只是节点和边的含义不同。以岛屿数量为例一张二维网格里值为 1 表示陆地0 表示水任务是统计有多少个连通的陆地块。暴力做法是两层循环遍历每个格子每遇到一个 1就把周围相连的 1 全部访问一遍并标记掉。这不是典型的搜索吗它的目标是一块连通区域里的所有陆地格子策略是从一个起点向上下左右扩散。一旦你用搜索树的视角去看代码自然分成两步外层循环负责驱动起点内层搜索负责扩散并染色。这类题的共同点在于目标不是一个单点而是一个集合或一组解。搜索的价值不是找到而是枚举并筛选出所有满足条件的结构。3.2 DFS 的递归骨架与现场还原DFS 的递归骨架长得非常固定visited set() def dfs(state): if state in visited: return visited.add(state) for next_state in neighbors(state): dfs(next_state)骨架本身不难难的是现场还原。在全排列问题里你选中一个数字后递归进入下一层下一层的可用集合已经少了这个数。如果递归返回后你不把这个数字放回候选列表下一个分支的选择就会错乱。这个撤销选择的操作就是回溯。现场还原最大的坑是 visited 集合的共享与清理。很多人把 visited 定义成全局变量递归过程中不断往里加状态却忘了每个分支结束后要把本分支新增的状态移除于是第一个分支走过的节点在第二个分支里变成已访问导致答案少了一大截。我的经验是写递归前先在脑内模拟三层递归的进栈与出栈重点问自己我进入下一层之前改了什么返回后应该恢复什么。凡是进入前修改的共享状态返回后必须逆操作恢复如果你用参数传递状态而不是用全局变量那通常不需要恢复因为每次递归调用自带一份新值。3.3 BFS 的层序推进与最短路径直觉DFS 和 BFS 最大的差别在于状态的扩展顺序。BFS 按层推进先把所有距离为 1 的状态扩展完再扩展距离为 2 的状态。这个特性让 BFS 天然适合求最短路径因为第一次访问到目标点时的层数就是最短距离。经典例子是迷宫最短步数从起点出发每一步能走到相邻空地问最少几步到终点。把每个坐标看成状态相邻坐标看成边BFS 第一次到达终点的那一层就是答案。模板也很固定def bfs(start, target): queue [start] visited {start} step 0 while queue: for _ in range(len(queue)): cur queue.pop(0) if cur target: return step for nxt in neighbors(cur): if nxt not in visited: visited.add(nxt) queue.append(nxt) step 1 return -1这里pop(0)只是便于演示实际工程里应该用collections.deque的popleft()否则队列头部的弹出是 O(n) 的数据一大性能就会崩。3.4 队列与栈的选择不是顺手是有原因的很多初学者困惑为什么 DFS 用递归而 BFS 用队列递归调用天然维护了一个系统栈每次调用都保存当前状态返回时自动弹出这和深度优先的一条路走到黑再回头天然匹配。BFS 则要求先进先出地扩展节点先被发现的节点必须先被检查完这正好就是队列的语义。你非要用栈模拟 BFS 也不是不行但扩展顺序一旦被打乱最短路径性质就丢了。这一讲的练习题里最推荐的组合是DFS 用于枚举所有可行解比如全排列、组合、子集BFS 用于求最小步数和最短路径比如迷宫、单词接龙、打开转盘锁。时刻记住这句话DFS 负责有多少种走法BFS 负责最快怎么走到。4. 从暴力搜索到高效搜索剪枝与双向BFS4.1 剪枝到底剪掉的是什么三类剪枝拆解暴力搜索的问题是状态数量呈指数增长。剪枝不是玄学它是在搜索树的某个节点提前判断这个分支不可能通向目标然后直接返回不再向下扩展。第六讲把剪枝拆成三类可行性剪枝当前状态已经明显不可能满足约束条件直接不递归。比如八皇后问题中当前位置与已有皇后冲突就不需要继续往下一行放棋子了。剪枝条件是硬约束被破坏。最优性剪枝记录当前已知的最优解一旦当前路径的代价已经超过或者不可能优于它立刻停止。比如旅行商问题里当前路径长度已经超过全局最优继续扩展只会更差。重复状态剪枝用 visited 集合或记忆化数组记录已经搜过的状态避免重复计算。前面 DFS 里的 visited 本质就是重复状态剪枝。三个类别不是孤立的一个高效的搜索实现经常同时叠加两到三层剪枝。判断剪枝是否有效的标准很简单剪枝只能砍掉不可能包含答案的分支绝不砍掉可能包含答案的分支。宁可少剪也不可错剪。4.2 双向BFS把爆炸指数变成两半单向 BFS 在状态空间很大时仍然会超时。双向 BFS 的思路很直接从起点和目标同时开始搜索两边各走一层当两边的访问区域相交时路径就找到了。为什么它快因为搜索树的规模是指数增长的。单向 BFS 要扩展到第 d 层节点量大约是分支因子 b 的 d 次方双向 BFS 从两端各扩展 d/2 层总量大约是两倍的 b 的 d/2 次方。当 b 比较大时这个差距极其可观。实现上维护两个队列、两个 visited 集合每次选择当前节点数较少的一端扩展一层。这个扩展节点少的一边的细节非常关键它能让整体开销进一步下降也是双向 BFS 面试考点里最容易丢分的地方。典型场景是单词接龙字典规模大分支因子不低单向 BFS 很容易被时间卡死双向 BFS 却常常能在几十毫秒内跑完。4.3 从八皇后到单词接龙组合优化题目的共同套路课后的练习里出镜率最高的两道题是八皇后和单词接龙。它们表面上毫无关系实际上共用同一套搜索框架定义状态、定义扩展方式、定义终止条件、剪枝加速。八皇后的状态是当前已放置皇后的列位置扩展方式是在下一行找一个与已有皇后都不冲突的列终止条件是放满 n 行单词接龙的状态是当前单词扩展方式是把当前单词变换一个字母得到字典里存在的另一个单词终止条件是等于目标单词。一旦你习惯了这套框架再遇到数独、解谜、路径规划都能快速画出状态树然后决定用 DFS 枚举还是 BFS 求最短。第六讲真正的精华也在这里搜索算法本身只有那么几种难的是把新问题翻译成旧框架能处理的形式。5. 这堂搜索课最容易踩的四个坑5.1 二分死循环的经典现场死循环最常见于求边界的模板中出现了left mid的写法。比如有人这样写while left right: mid (left right) // 2 if nums[mid] target: left mid else: right mid当 left 和 right 相邻时mid 向下取整会一直等于 left如果nums[mid] targetleft 原地震动循环永远出不来。修法有两个把left mid改成left mid 1或者把 mid 改成上取整mid (left right 1) // 2。排查这类问题时盯屏幕看是没用的。手动拿两个相邻数走一遍循环立刻能看出 left 和 right 是否在某个瞬间不再变化。5.2 DFS 忘记恢复状态导致答案互相污染全排列、组合这类题目里修改了全局候选状态后递归返回时必须把修改撤销。一旦漏掉这一步第一个分支把某个数标记为已用后续分支就用不了这个数输出结果会莫名少一大截。排查办法在 dfs 返回后立刻打印当前的可选集合和已选状态看看是否和进入递归前一致。更本质的做法是养成对称的代码习惯——任何共享可变状态在进入递归前被修改递归返回后必须有对应的还原语句而且这两行要写在结构对称的位置一眼就能看出来。5.3 BFS 的 visited 标记时机入队标记还是出队标记很多人写 BFS 时把 visited 判断放在出队那一刻结果同一个节点被反复入队队列越来越长甚至死循环。正确做法是入队即标记。一旦一个节点被放进队列它就已经在待搜索集合里了后续其他邻居完全有可能再次生成它。如果等到出队时才标记它在队列里等待的这段时间里四面八方都会往队列里塞它的重复副本。层级遍历里还有一个配套细节for _ in range(len(queue))必须在每层开始时先取当前队列长度不能把len(queue)写进循环内部反复求值否则队列一边扩展一边读取层数边界就全乱了。5.4 递归深度过大搜索树很大系统栈很小DFS 写起来最顺手但状态一多就容易栈溢出。尤其是搜索树深度很高的场景比如超长数组全排列、大规模棋盘路径搜索递归层数动辄成千上万默认的系统栈往往只有几千层直接爆掉。这时候有两条出路改成显式栈模拟 DFS或者换层数更可控的 BFS。不要硬扛。另外还有一个总被忽略的问题同样一个子状态如果从多条路径都能到达而你不知道保存结果就是在反复做无用功。第六讲在最后专门强调了记忆化搜索——它不改变搜索顺序只是把算过的子状态结果存下来后面再次遇到直接查表很多指数级问题就是这么被拉回多项式复杂度的。最后分享一个我带学员时一直坚持的习惯拿到任何搜索题先别急着写代码花三分钟把状态树画出来。状态是什么从它能走到哪些新状态哪个分支注定没有答案这条树画清楚了代码就是照着树翻译而已。大部分人的搜索代码出问题都是因为状态定义还没想明白就动手写循环。我自己早期写回溯经常漏掉还原后来强制自己画树 模拟三层栈之后错误率才明显降下来。如果你正在跟着这个系列刷题建议把这一讲的几个模板抄下来再每天挑一道搜索题专门练边界和剪枝。搜索这个基础打牢了后面学动态规划、图论的时候你会感谢第六讲。