Swift算法俱乐部中文版 -- 线性搜索

2017-01-14 10:24:20来源:http://www.jianshu.com/p/c1fd13b323f9作者:云抱住阳光太阳没放弃发亮人点击

目标:在数组中查找特定值。


我们有一个对象的数组。使用线性搜索,我们遍历数组中的所有对象,并将每个对象与我们要查找的对象进行比较。如果两个对象相等,我们停止搜索并返回当前数组的索引。如果没有,我们继续寻找下一个对象,直到所有对象都被搜索。


举个栗子

假设我们有一个数字数组 [5, 2, 4, 7] ,我们想检查数组是否包含数字 2


我们首先比较数组中的第一个数字, 5 ,去和 2 比较,它们显然不一样,所以我们继续下一个数组元素。


我们将数组的第2个元素 22 进行比较,注意它们是相等的。现在我们就可以停止搜索并返回数组索引 1 了。


代码
func linearSearch<T: Equatable>(_ array: [T], _ object: T) -> Int? {
for (index, obj) in array.enumerated() where obj == object {
return index
}
return nil
}

在 playground 中测试:


let array = [5, 2, 4, 7]
linearSearch(array, 2) // 返回 1

性能

线性搜索的性能是 O(n) ,它会比较数组中的每个元素,所需的时间与数组的长度成正比。在最坏的情况下,我们需要查看数组中的所有元素。


最好的情况是 O(1) ,但这种情况很罕见,我们寻找的元素正巧在数组的最开头,会在第一次比较中被找到。你可能会幸运,但大部分时间你不会。 平均来说,线性搜索需要查看数组中一半的对象。


作者:Patrick Balestra


英文链接:
https://github.com/raywenderlich/swift-algorithm-club/blob/master/Linear%20Search/README.markdown




最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台