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

搜索算法

｜

91

搜索算法

search (C,t)

iter = C.begin()

while iter

≠

C.end() do

❷

e = iter.next()

❸

if e = t then

return true

return false

end

❶

按照从

0

到

n

- 1

的顺序访问每个元素。

❷

迭代器一直访问每个元素直到最后一个元素为止。

❸

从

迭代器

中一个接一个地取出元素。

5.1.2 使用环境

有时你需要在一个不知道是否有序的集合中频繁地查找元素。如果无法获取该集合的信

息，那么采用

顺序查找

是一个不错的方法，它以穷举集合中每个元素的方式来完成这项

工作。如果集合只能通过迭代器来访问，那么顺序搜索就是唯一能使用的搜索算法。

如果集合无序并且以链表的形式存储，那么插入元素需要常数时间（简单插入表尾即可）。

但是如果需要频繁地将元素插入数组中，那么这时就需要需要动态地管理数组。这个特

性要么由编程语言提供，要么由程序员自己实现。无论如何，搜索一个元素的期望时间

是

O

(

n

)

，因此，找到并且移除一个元素需要至少

O

(

n

)

的时间。

顺序搜索

在对于能搜索的元素类型几乎没有限制。唯一的要求就是必须有一个匹配函数

来决定当前元素是否就是目标元素。通常匹配函数交由元素自己计算管理。

5.1.3 解决方案

顺序搜索

的实现非常最简单。例

5-1

给出了顺序搜索的

Python

实现。

例

5-1

：顺序搜索的

Python

实现

def sequentialSearch(collection, t):