Hello 算法搜索篇总结：四大类搜索算法的效率对比、选型策略与源码实现

本文基于《Hello 算法》（hello-algo）英文版搜索篇的章末总结（en/docs/chapter_searching/summary.md）展开，系统梳理暴力搜索、二分查找、哈希查找与树搜索四类方法的原理、时间复杂度与适用场景，并结合仓库中 en/codes/python/chapter_searching/ 目录下的 Python 参考实现，帮助读者掌握"根据数据规模、查询/更新频率选择搜索方法"的决策框架，以及"用哈希替换线性查找优化时间复杂度"这一核心实战技巧。

一、总结的核心结论：两类搜索路线

搜索篇的总结首先给出了一个关键分类：所有搜索算法可按实现思路划分为两条路线。

第一条路线：通过遍历数据结构定位目标（暴力搜索 / Brute-force Search）

• 线性查找适用于数组、链表等线性结构，从一端逐元素访问，直到命中目标或遍历完毕；
• **广度优先搜索（BFS）与深度优先搜索（DFS）**适用于图与树：BFS 从初始节点出发逐层搜索、由近及远；DFS 沿路径深入到底再回溯尝试其他路径。

这类算法的优点是简单、通用性好，不需要任何数据预处理或额外数据结构；缺点是时间复杂度为 $O(n)$（$n$ 为元素个数），数据量大时性能较差。

第二条路线：利用数据的组织方式或先验信息高效定位（自适应搜索 / Adaptive Search）

• 二分查找利用数据的有序性，仅适用于数组；
• 哈希查找用哈希表以键值对形式存储待查数据；
• 树搜索作用于二叉搜索树等特定树结构，通过比较节点值快速剪枝。

这类算法效率很高，时间复杂度可达 $O(\log n)$ 甚至 $O(1)$，但通常需要数据预处理：二分查找要求数组预先排序，哈希查找与树搜索则需要额外数据结构来维护，附带额外的时间与空间开销。在书中它们也常被称为"查找算法（lookup）"，主要用于在特定数据结构中快速检索目标元素。这一分类的详细阐述见 searching_algorithm_revisited.md。

二、线性查找：O(n) 的通用解法

总结指出线性查找"适用于小规模数据或更新频繁的数据"。仓库中的 linear_search.py 给出了数组与链表两种载体上的实现：

def linear_search_array(nums: list[int], target: int) -> int:
    """Linear search (array)"""
    # Traverse the array
    for i in range(len(nums)):
        if nums[i] == target:  # Found the target element, return its index
            return i
    return -1  # Target element not found, return -1

对链表则沿 next 指针逐节点推进，找到目标节点后返回节点对象（而非下标），体现"链表查找结果通常是节点引用"这一与数组的本质差异。从源码结构看，两种实现都只有一次循环，无额外空间开销（空间复杂度 $O(1)$），最差情况需要比较 $n$ 次——这正是总结中"无需预处理但时间复杂度 $O(n)$"这一判断的直接来源。

三、二分查找：有序数组上的 O(log n) 解法

总结第一条要点即：二分查找依赖有序数据，通过不断将搜索区间减半来定位目标，要求输入已排序且仅适用于数组或基于数组的结构。仓库中的 binary_search.py 同时给出了闭区间与左闭右开区间两种写法：

def binary_search(nums: list[int], target: int) -> int:
    """Binary search (closed interval)"""
    # Initialize closed interval [0, n-1]
    i, j = 0, len(nums) - 1
    while i <= j:
        m = (i + j) // 2  # Calculate midpoint index m
        if nums[m] < target:
            i = m + 1  # target is in the interval [m+1, j]
        elif nums[m] > target:
            j = m - 1  # target is in the interval [i, m-1]
        else:
            return m
    return -1

关键细节有两点，均可从源码注释与文档中确认：

1. 中点计算防溢出：在 C/C++ 等语言中 $i+j$ 可能超出 int 范围，规范做法是使用 $m=\lfloor i+(j-i)\mathrm{/}2\rfloor$（详见 binary_search.md）；Python 整数无固定位宽，因此注释中特别说明"无需考虑大数溢出"；
2. 区间表示的一致性：闭区间写法下循环条件为 i <= j，收窄操作 i = m + 1 / j = m - 1 左右对称；而左闭右开区间 [i, j) 的写法（binary_search_lcro）循环条件为 i < j，右边界收窄写作 j = m。书中推荐闭区间写法，因其更不易出错。

二分查找的代价与收益在总结与正文中对应：

• 收益：每轮迭代区间减半，时间复杂度 $O(\log n)$。举例来说，$n = 2^{20}$ 时线性查找需约 $10^6$ 次迭代，而二分查找只需 20 次；且无需额外空间，空间复杂度 $O(1)$。
• 代价：仅适用有序数据——若为排序付出 $O(n \log n)$ 的预处理成本，且插入频繁时维持有序数组每次需 $O(n)$ 移动元素，得不偿失；另外二分查找依赖"跳跃式"随机访问，链表上这种访问方式低效，因此不适合链表。

四、哈希查找：O(1) 的查询利器

总结指出哈希查找"适合高查询效率且不需要范围查询的场景"。hashing_search.py 展示了其工作方式：先用一趟遍历把"元素 → 下标（或节点对象）"写入哈希表，之后每次查询都是直接的键查找：

def hashing_search_array(hmap: dict[int, int], target: int) -> int:
    """Hash search (array)"""
    # If this key does not exist in the hash table, return -1
    return hmap.get(target, -1)

从源码结构看，查询函数本身只是一次 dict.get 调用，这正是 $O(1)$ 平均查询复杂度的体现。其代价在总结中同样明确：哈希表需要 $O(n)$ 额外空间，无法维护数据有序性，因此不适合需要有序数据或范围查询的场景，且性能依赖于哈希函数与冲突处理策略。

五、树搜索与效率总表

总结中"树搜索适合必须保持有序并支持范围查询的大规模动态数据集"这一论断，依据可在 searching_algorithm_revisited.md 的效率对比表中找到完整数据：

操作	线性查找	二分查找	树搜索	哈希查找
查找元素	$O(n)$	$O(\log n)$	$O(\log n)$	$O(1)$
插入元素	$O(1)$	$O(n)$	$O(\log n)$	$O(1)$
删除元素	$O(n)$	$O(n)$	$O(\log n)$	$O(1)$
额外空间	$O(1)$	$O(1)$	$O(n)$	$O(n)$
数据预处理	无	排序 $O(n \log n)$	建树 $O(n \log n)$	建哈希表 $O(n)$
数据有序性	无序	有序	有序	无序

树搜索的两个关键特性值得注意：

• 树节点在内存中非连续存储，因此适合超大规模数据集，且天然支持有序数据与范围查询；
• 连续插入/删除可能使二叉搜索树退化（偏斜），时间复杂度退化为 $O(n)$；若采用 AVL 树或红黑树，所有操作可稳定保持在 $O(\log n)$，代价是维护树平衡的额外开销。

六、如何选择搜索方法：总结给出的决策框架

总结的核心实战结论是：实际选型需要综合分析数据规模、搜索性能要求、查询与更新频率三个因素。整理为场景对照如下（均出自 summary.md 与 searching_algorithm_revisited.md）：

线性查找

• 通用性好，无需任何预处理；若只查询一次，其他三种方法的前置成本（排序、建表、建树）可能超过一次线性查找本身；
• 适合数据量小的场景，时间复杂度的影响有限；
• 适合数据更新频率高的场景，因为它不需要维护任何附加结构。

二分查找

• 适合大规模、已排序的数据集，最坏情况性能稳定在 $O(\log n)$；
• 数据量不宜"过大到无法装入连续内存"，因为数组需要连续存储空间；
• 不适合频繁的插入/删除场景——维护有序数组的开销高。

哈希查找

• 适合查询性能要求高的场景，平均时间复杂度 $O(1)$；
• 不适合需要有序数据或范围搜索的场景；
• 对哈希函数与冲突处理策略敏感，存在性能退化风险；
• 不适合过大的数据量，因为哈希表需要预留额外空间来降低冲突率。

树搜索

• 适合海量数据集（节点非连续存储）；
• 适合需要维持有序或执行范围查询的场景；
• 需注意二叉搜索树退化为 $O(n)$ 的风险，必要时改用平衡树。

七、实战技巧：用哈希替换线性查找

总结最后一条要点是本篇最值得记住的优化策略：用哈希查找替换线性查找，把 $O(n)$ 的查找降为 $O(1)$。书中以"两数之和"问题为例，two_sum.py 给出了两种解法的对照：

暴力法（双重循环枚举，$O(n^2)$ 时间 / $O(1)$ 空间）

def two_sum_brute_force(nums: list[int], target: int) -> list[int]:
    """Method 1: Brute force enumeration"""
    for i in range(len(nums) - 1):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

哈希表法（单循环，$O(n)$ 时间 / $O(n)$ 空间）

def two_sum_hash_table(nums: list[int], target: int) -> list[int]:
    """Method 2: Auxiliary hash table"""
    dic = {}
    for i in range(len(nums)):
        if target - nums[i] in dic:
            return [dic[target - nums[i]], i]
        dic[nums[i]] = i
    return []

哈希法的精髓在于"查插同步"：对每个 nums[i]，先在表中查询互补值 target - nums[i] 是否已出现，命中即返回；未命中再把当前元素写入表。由此把内层循环的线性扫描（每次 $O(n)$，累计 $O(n^2)$）压缩为一次哈希查询（平均 $O(1)$），整体从 $O(n^2)$ 降到 $O(n)$。虽然需要 $O(n)$ 额外空间，但书中文档 replace_linear_by_hashing.md 的结论是：这是"时空更均衡的总体最优解"——以可控的空间换数量级的时间提升。

八、要点回顾

1. 二分查找依赖有序数据、仅适用于数组类结构，通过不断对半收缩区间实现 $O(\log n)$ 查找，空间复杂度 $O(1)$；
2. 暴力搜索（线性查找、BFS、DFS）通用且免预处理，但时间复杂度 $O(n)$，适合小数据或高频更新场景；
3. 哈希查找与树搜索将效率提升到 $O(1)$ / $O(\log n)$，代价是额外数据结构与维护成本；哈希查找不能支持范围查询，树搜索需注意偏斜退化；
4. 选型时综合权衡数据规模、查询性能要求、查询与更新频率，没有"总是最优"的方案；
5. 工程上最常用的高性价比优化是以哈希替换线性查找，典型如"两数之和"从 $O(n^2)$ 优化到 $O(n)$。

相关实现均可在 en/codes/python/chapter_searching/ 目录中直接运行验证；二分查找的区间写法对比、插入位置查找（binary_search_insertion.md）与左右边界查找（binary_search_edge.md）等变体问题，可作为掌握本章节后的进阶练习。