目標(biāo)：在數(shù)組中查找特定值青柄。
我們有一個(gè)對(duì)象的數(shù)組。使用線性搜索乓旗，我們遍歷數(shù)組中的所有對(duì)象府蛇，并將每個(gè)對(duì)象與我們要查找的對(duì)象進(jìn)行比較。如果兩個(gè)對(duì)象相等屿愚，我們停止搜索并返回當(dāng)前數(shù)組的索引汇跨。如果沒(méi)有，我們繼續(xù)尋找下一個(gè)對(duì)象妆距，直到所有對(duì)象都被搜索穷遂。
舉個(gè)栗子
假設(shè)我們有一個(gè)數(shù)字?jǐn)?shù)組 [5, 2, 4, 7] ，我們想檢查數(shù)組是否包含數(shù)字 2 娱据。
我們首先比較數(shù)組中的第一個(gè)數(shù)字蚪黑， 5 ，去和 2 比較中剩，它們顯然不一樣忌穿，所以我們繼續(xù)下一個(gè)數(shù)組元素。
我們將數(shù)組的第2個(gè)元素 2 與 2 進(jìn)行比較结啼，注意它們是相等的÷咏＃現(xiàn)在我們就可以停止搜索并返回?cái)?shù)組索引 1 了。
代碼
func linearSearch<T: Equatable>(_ array: [T], _ object: T) -> Int? {
for (index, obj) in array.enumerated() where obj == object {
return index
}
return nil
}
在 playground 中測(cè)試：
let array = [5, 2, 4, 7]
linearSearch(array, 2) // 返回 1
性能
線性搜索的性能是 O(n) 郊愧，它會(huì)比較數(shù)組中的每個(gè)元素朴译，所需的時(shí)間與數(shù)組的長(zhǎng)度成正比。在最壞的情況下属铁，我們需要查看數(shù)組中的所有元素眠寿。
最好的情況是 O(1) ，但這種情況很罕見(jiàn)焦蘑，我們尋找的元素正巧在數(shù)組的最開(kāi)頭盯拱，會(huì)在第一次比較中被找到。你可能會(huì)幸運(yùn)，但大部分時(shí)間你不會(huì)坟乾。 平均來(lái)說(shuō)迹辐，線性搜索需要查看數(shù)組中一半的對(duì)象。
英文鏈接：
https://github.com/raywenderlich/swift-algorithm-club/blob/master/Linear%20Search/README.markdown
