算法技术手册（原书第2 版）

89

第

5

章

搜索算法

给定一个集合

C

，我们可以执行下述两个基本查询：

存在性查询

集合

C

中包含某个给定的元素吗？通常，我们只想知道集合

C

中是否包含特定元素

t

。

如果

t

存在，那么查询结果为真；否则，查询结果为假。

相关性查询

返回集合

C

中和目标键值

k

相关联的信息。通常键会与一个较为复杂的数据结构关

联在一起，我们将该数据结构称为“值”。这种查询通常是为了获取或者替换该值。

本章还会介绍如何使用一些数据结构来高效地处理搜索请求。当然，读者也许会考虑使

用第

4

章介绍的排序算法对集合

C

进行排序然后进行查找。这样搜索的效率固然会得到

改善，但同时也需要大量的额外费用去维护集合有序。尤其是在需要对集合中的元素进

行频繁的删除和插入操作时，大量的额外费用将会抵消排序搜索带来的好处。

不管如何，算法的性能最终取决于它检查了多少个元素。下面提供了一些简单的策略来

选择搜索算法。

小数据集

顺序搜索

的实现最为简单，而且内建于很多编程语言之中。只有在这个数据集只能

使用

迭代器

顺序访问的时候才会选择顺序搜索。

受限内存

如果集合是一个数组且保持不变，那么使用

二叉搜索

可以减少内存的使用。

动态数据集

如果集合中的元素改变频繁，那么基于

散列的搜索

或者

二叉搜索树

都是一个不错的

主意。两种算法都可以巧妙地使用数据结构减少费用。