搜索算法

“搜索”涵盖多种问题：在序列中定位值、查询有序集合、按键查找，或在图中发现可达顶点。先选择表示，再选择算法。

决策地图

场景	方法	典型查询成本	主要要求
单次扫描无序数据	线性搜索	$O(n)$	相等性测试
可随机访问的有序序列	二分搜索	$O(\log n)$	维持顺序
反复精确键查找	哈希表	期望 $O(1)$	哈希和额外空间
有序动态集合 / 范围	平衡搜索树	$O(\log n)$	维护树结构
深入探索 / 依赖结构	DFS	$O(V+E)$	访问状态
无权图中的最少边路径	BFS	$O(V+E)$	队列和访问状态

这些成本假定常规实现。哈希表最坏情况不是常数，失衡搜索树也可能退化到线性高度。

摊销预处理

为了二分搜索而先排序需要 $O(n\log n)$。如果查询很多，或同时需要有序操作，这项投入很有价值；若只查一次，通常得不偿失。类似地，哈希表用构建时间和内存换取反复精确键查询。

搜索通常是边界问题

二分搜索可以从“找到这个值”推广到“找到单调谓词首次为真的位置”。DFS 和 BFS 也只有在明确输出契约后才真正有用：存在性、遍历顺序、父节点、距离、连通分量，或一条见证路径。

计算整个工作负载

静态数组上执行 $q$ 次查询，重复线性扫描需要 $O(qn)$；排序一次再二分搜索需要 $O(n\log n+q\log n)$，还应计入必要的复制或原下标保留成本。在单位成本模型下，两者大致在对数数量级的全扫描查询附近交叉，但这不是通用的实测阈值。频繁更新会改变计算：bisect 可以对数时间找到位置，但往有序数组中插入仍需移动 $O(n)$ 个元素。

查找示例返回位置或插入边界，图遍历则返回可达顶点和路径信息。在邻接表分析中，$V$、$E$ 表示遍历部分的顶点数、边数，不是序列长度。从一个起点遍历不会覆盖不连通的部分。若只问是否存在，提前停止可能节省工作；若要求所有可达顶点或所有距离，就需要完成遍历。

来源

• Open Data Structures
• Python bisect

我的阅读 · 打开过的笔记会记在当前浏览器里。