首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》结论

关灯直达底部

对于无序的小集合来说,顺序查找是最容易实现的并且总体上很有效率。最坏情况是你要寻找的元素不在集合中,因为你需要检查集合中的每一个元素。如果查找的结果普遍都是假,那么你需要考虑一下使用一个不同的查找算法,即使集合相对来说比较小。

有些时候,一个已索引的集合也许会有一些“空洞”。也就是说,集合中有一些索引指向的是空元素[1]。在这样的情况下,你需要在实现中添加代码来检查索引值,确保其指向的元素不为空。我们将例5-1的代码加上了额外的校验,如例5-4所示。

例5-4:增加了校验空元素的顺序查找

如果时间要求很高并且集合很大,那么元素之间的额外比较就需要引起注意,所以这里存在另外一个解法。不在空槽中放入nil,而是放入一个特定的标记元素。当检查这个标记是否和其他元素相等时候总是返回假。例如,如果已知寻找的t是一个正整数,那么你可以使用-1作为标记来避免额外的比较[2]。

[1]更确切地说,数组的第i个元素A[i]可能等于一个特定值nil。对于数组来说通过迭代器访问来给出nil值的用法很少见。 [2]在Ruby中,nil可以和任何对象进行值比较。这意味着在示例5-4中额外的比较实际上是不需要的。