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

90

｜

第

5

章

顺序访问

二叉搜索树

可以在维护一个

动态数据集

的同时，还能按顺序处理集合中的元素。

不要忘了考虑一些初始化数据结构所需要的费用。选择合适的数据结构不仅能够改善单

个查询的性能，还能在数据不断变化以及数据中元素被频繁访问时，减少维护数据结构

的费用。

在讨论本章的算法之前，我们假设存在一个集合

U

，集合

C

是

U

的一个子集，目标元素

t

是

U

的一个元素。如果

t

是一个键，那么

U

是一个可能的键集合，其中

k

∈

U

，而且

集合

C

可能会包含更多复杂的元素。不仅如此，由于

C

中可能会包含重复元素，因此没

有办法在此基础上构建一个集（

Set

）。

假设

C

中的元素可以通过下标随机访问，这里使用数组

A

表示集合，用

A

[

i

]

表示集合中

的第

i

个元素。为了方便起见，我们用值

null

来表示元素不在

U

中。当查询需要查找

的特定元素不在集合中时，这个值的用处就显现出来了。一般来说，假设集合中不存在

值

null

。

5.1 顺序搜索

顺序搜索

，又 称 线性搜索，是最简单的搜索算法。它查找目标元素

t

的方式非常简单粗暴，

即从集合中的第一个元素开始，不断检查每一个元素，直至找到匹配的元素或者检查完

集合中的所有元素。

必然存在某种方法可以获取集合中待查找元素，并且不关心具体顺序。通常，集合

C

只

能通过一个只读的

迭代器

来访问其中的每个元素，例如

SQL

查询中使用的游标（

cursor

）。

5.1.1 输入 / 输出

输入包括一个具有

n

（

n

> 0

）个元素的非空集合

C

，以及待查找的元素

t

。如果

t

在

C

中，

那么返回

true

；否则，返回

false

。

顺序搜索算法小结