05. 查找

查找

1. 基本概念

• 查找：在数据结构中确定给定值是否存在，并返回其位置
• 查找表：静态查找表、动态查找表

2. 顺序查找法

• 逐个比较，适合无序表，时间复杂度 O(n)

3. 分块查找法

• 将表分为若干块，块内顺序查找，块间用索引，适合大表

4. 折半查找法（二分查找）

• 适合有序表，每次折半，时间复杂度 O(log n)

5. B 树及 B+树

• B 树：多路平衡查找树，适合磁盘存储
• B+树：所有关键字都在叶子节点，适合范围查找

6. 散列（哈希）表

• 散列函数、冲突处理（开放定址、链地址法）
• 查找效率高，接近 O(1)

7. 字符串模式匹配

• 朴素算法、KMP 算法等

8. 查找算法分析与应用

• 查找效率、空间复杂度、适用场景

练习题

1. 简述顺序查找和折半查找的适用条件和效率。
2. 分块查找的基本思想是什么？
3. B 树和 B+树有何区别？
4. 哈希表如何处理冲突？
5. 字符串模式匹配常用算法有哪些？