查找算法

查找是计算机科学中最常见的操作之一。本部分涵盖静态查找表、动态查找树与哈希表三大类查找结构，从 $O(n)$ 的顺序查找到 $O(\log n)$ 的有序表和树形查找，再到期望 $O(1)$ 的哈希查找，帮助理解不同查找策略的设计原理、复杂度分析与适用场景。

内容导航

• 顺序查找

  逐个比较线性表中的元素，适用于无序数据，时间复杂度为 $O(n)$。

• 二分查找

  在有序表中反复折半，处理基础查找、左右边界和插入点，时间复杂度为 $O(\log n)$。

• 插值查找

  按关键字分布比例估算探测位置，适用于均匀分布的有序表。

• 斐波那契查找

  使用斐波那契数列分割查找区间，只依赖加减运算完成区间收缩。

• 静态树表查找

  将静态有序表组织成判定树，用平均查找长度衡量查找效率。

• 索引顺序表查找

  先通过索引定位数据块，再在块内顺序查找，折中索引开销与查找效率。

• 二叉搜索树

  动态查找表，支持查找、插入、删除，平均效率为 $O(\log n)$。

• AVL 树

  高度平衡的二叉搜索树，通过旋转维持平衡，保证查找效率。

• B-树与 B+树

  面向外存和多级索引的多路平衡搜索树，适合大规模范围查询。

• Trie 字典树

  按字符路径组织字符串集合，适合前缀匹配和词典检索。

• 哈希表查找

  通过哈希函数映射槽位，合理处理冲突后期望查找时间为 $O(1)$。

• 综合项目

  综合使用多类查找结构完成校园资料检索和性能横向对比。