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

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

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

举个栗子

---

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

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

我们将数组的第2个元素 2 与 2 进行比较，注意它们是相等的。现在我们就可以停止搜索并返回数组索引 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