查找算法
目录
- 顺序查找：简单，适合小数据或无序集合，使用
find或position- - 二分查找：高效，适合有序数据，使用
binary_search- - 哈希查找：快速，适合键值对或存在性检查，使用
HashMap/HashSet- - 字符串查找 ：
KMP等算法适用于模式匹配 - 高级场景：根据需求实现插值查找、并行查找等
顺序查找
当数据项存储在诸如Vec，数组，切片这样的集合中时，数据具有线性关系，因为每个数据项都存储在相对于其他数据项的位置。
在切片中，这些相对位置是数据项的索引值。由于索引值是有序的，可以按顺序访问，所以这样的数据结构也是线性的。
回想前面学习的栈，队列，链表都是线性的。基于这种和物理世界相同的线性逻辑，一种很自然的查找技术就是线性查找，或者叫顺序查找
- 原理：逐一比较集合元素与目标值，直到找到或遍历结束。
- 时间复杂度：平均/最坏
O(n)，最好O(1)。 - 空间复杂度：
O(1)，仅需常数空间。 - 适用场景：无序数据、小规模数据、单次查找。
- 优点：实现简单、无需排序、支持任意数据类型。
- 缺点：效率低，不适合大数据或频繁查找。
- Rust 实现：使用
iter().position()或find()，支持泛型，安全高效。
二分查找
二分查找是一种高效的查找算法，适用于有序数据集合。 其基本思想是将查找区间不断减半，通过比较中间元素与目标值的大小，决定继续在左半部分还是右半部分查找，直到找到目标值或查找区间为空。
- 原理：在有序集合中，比较中间元素与目标值，根据大小关系排除一半元素，重复直到找到或范围为空。
- 时间复杂度：平均/最坏
O(log n)，最好O(1)。 - 空间复杂度：
O(1)（迭代实现），O(log n)（递归实现）。 - 适用场景：有序数组或切片、大规模数据、频繁查找。
- 优点：高效，适合大数据量，时间复杂度低。
- 缺点：要求数据预先排序，不适用动态数据或无序集合。
- Rust 特性：标准库提供
binary_search等API，泛型支持，安全高效。
哈希查找
哈希查找是一种基于哈希表的数据结构（如 HashMap 或 HashSet）的查找算法，通过将键映射到哈希值实现快速定位
（这里以线性探测法为例）
- 原理：通过哈希函数将键映射到索引，访问哈希表中的槽位查找值。
- 时间复杂度：
- 平均：
O(1)（假设哈希函数均匀，冲突少）。 - 最坏：
O(n)（冲突严重时，退化为线性查找）。
- 平均：
- 空间复杂度：
O(n)，存储键值对或元素。 - 适用场景：快速键值映射、检查元素存在性、频繁查找。
- 优点：平均情况下极快，适合动态数据。
- 缺点：依赖哈希函数质量，冲突可能降低性能，空间开销较大。
- Rust 特性：标准库提供
HashMap和HashSet，高效、安全，支持泛型
字符串查找
字符串查找是计算机科学中的一个重要领域，涉及在文本中查找特定模式或子字符串的方法。
其中，KMP（Knuth-Morris-Pratt）算法是一种高效的字符串查找算法，适用于模式匹配。
以下是常用的字符串查找算法及其特点：
- 朴素算法
(Naive String Matching)：- 原理：逐位比较主串和模式串的所有可能位置。
- 时间复杂度：
O(m * n)，m为模式串长度，n为主串长度。 - 空间复杂度：
O(1)。 - 优点：简单，无需预处理。
- 缺点：效率低，尤其当主串和模式串长且匹配失败频繁时。
KMP算法(Knuth-Morris-Pratt)：- 原理：利用模式串的前缀信息（部分匹配表），避免重复比较已匹配的部分。
- 时间复杂度：
O(m + n)，预处理O(m)，查找O(n)。 - 空间复杂度：
O(m)，存储部分匹配表。 - 优点：高效，适合长字符串，避免回溯。
- 缺点：实现稍复杂，需预处理。
并行查找
- 原理：利用多线程并行搜索子区间，适合大规模数据或多核环境。
- 时间复杂度：
- 平均：
O(n/p + log p)，其中 p 是线程数。 - 最好：
O(n/p)（均匀分布）。 - 最差：
O(n)（单线程退化）。
- 平均：
- 空间复杂度：
O(p)，存储线程和结果。 - 优点：利用多核加速，适合大数据查找。
- 缺点：线程开销大，小数据集性能可能不如单线程。
- 适用场景：大规模排序数组，多核处理器环境。