常见的搜索算法可分为基础查找算法、树结构搜索、图搜索和特殊结构搜索四大类，以下是主要分类及典型算法：

一、基础查找算法

  1. 线性搜索（Linear Search）

    • 实现方式：逐个遍历元素
    • 时间复杂度：O(n)
    • 适用场景：无序数据集合

  2. 二分搜索（Binary Search）

    • 实现方式：基于有序数组的折半查找
    • 时间复杂度：O(logn)
    • 变体：插值搜索（按分布比例预测位置）、指数搜索（先确定范围再二分）

二、树结构搜索

  1. 二叉搜索树（BST）

    • 特点：左子树值 < 根节点 < 右子树值
    • 时间复杂度：平均 O(logn)，最差 O(n)（退化为链表时）

  2. 平衡树系列

    • AVL 树：严格平衡，通过旋转保持高度差 ≤1
    • 红黑树：近似平衡，插入/删除效率更高
    • B/B+ 树：多路平衡，专为磁盘存储设计（数据库索引）

  3. 堆结构搜索

    • 特点：仅能快速访问堆顶元素（最大/最小值）
    • 应用：优先队列、Top K 问题

三、图搜索算法

  1. 广度优先搜索（BFS）

    • 实现：队列辅助，层序遍历
    • 应用：最短路径（未加权图）、社交网络关系搜索

  2. 深度优先搜索（DFS）

    • 实现：栈辅助（递归/迭代）
    • 应用：拓扑排序、连通分量检测

  3. A* 算法

    • 特点：启发式搜索，综合实际代价和预估代价
    • 应用：游戏 AI 路径规划、地图导航

四、特殊结构搜索

  1. 哈希查找

    • 特点：通过哈希函数直接定位桶
    • 时间复杂度：平均 O(1)，冲突时可能退化为 O(n)
    • 冲突处理：链地址法、开放寻址法

  2. 跳表（Skip List）

    • 特点：多层索引加速查找
    • 时间复杂度：O(logn)，媲美平衡树
    • 应用：Redis 有序集合

  3. 布隆过滤器（Bloom Filter）

    • 特点：概率型数据结构，判断「可能存在」或「一定不存在」
    • 应用：缓存穿透防护、爬虫 URL 去重

五、算法对比

算法 时间复杂度 空间复杂度 数据要求
线性搜索 O(n) O(1) 无
二分搜索 O(logn) O(1) 必须有序
哈希查找 O(1) O(n) 需要哈希函数
BFS/DFS O(V+E) O(V) 图结构
红黑树搜索 O(logn) O(n) 动态数据集合

六、选择建议

  • 小规模无序数据：线性搜索
  • 静态有序数据：二分搜索
  • 动态数据集合：平衡树（如红黑树）
  • 极速查询场景：哈希表（需处理冲突）
  • 路径/关系分析：BFS/DFS
  • 海量数据去重：布隆过滤器

七、工程实践建议

数据规模 推荐算法 典型场景
n ≤ 20 线性搜索 配置参数、枚举值查找
20 < n ≤ 100 实测对比选择 用户标签、本地缓存查询
n > 100 二分/哈希 数据库索引、大型数据集