【譯】Swift演算法俱樂部-二分搜尋
本文是對 ofollow,noindex">Swift Algorithm Club 翻譯的一篇文章。
Swift Algorithm Club 是 raywenderlich.com 網站出品的用Swift實現演算法和資料結構的開源專案,目前在GitHub上有18000+:star:️,我初略統計了一下,大概有一百左右個的演算法和資料結構,基本上常見的都包含了,是iOSer學習演算法和資料結構不錯的資源。
:octopus: andyRon/swift-algorithm-club-cn 是我對Swift Algorithm Club,邊學習邊翻譯的專案。歡迎有興趣學習演算法和資料結構,有時間的小夥伴一起參與翻譯,歡迎issue,或者直接提交pull request。
本文的翻譯原文和程式碼可以檢視:octopus: swift-algorithm-club-cn/Binary Search
目標:在陣列中快速尋找一個元素。
假設你有一個數字陣列,你想確定一個特定的數字是否在該陣列中,如果在,那麼獲得這個數字的索引。
對於上面的情況,Swift的 indexOf()
函式足夠完成:
let numbers = [11, 59, 3, 2, 53, 17, 31, 7, 19, 67, 47, 13, 37, 61, 29, 43, 5, 41, 23] numbers.indexOf(43)// returns 15
內建的 indexOf()
函式執行的是 線性搜尋 。程式碼大概是:
func linearSearch<T: Equatable>(_a: [T],_key: T) -> Int? { for i in 0 ..< a.count { if a[i] == key { return i } } return nil }
使用如下:
linearSearch(numbers, 43)// returns 15
有什麼問題呢? linearSearch()
從頭開始遍歷整個陣列,直到找到你正在尋找的元素。 在最壞的情況是數值不在陣列中,那麼之前的遍歷就白費。
平均而言,線性搜尋演算法需要檢視陣列中一半的值。 如果您的陣列足夠大,這將會變得非常慢!
分而治之
提升速度的經典方法是使用 二分搜尋 。 訣竅是將陣列分成兩半,直到找到值。
對於大小為 n
的陣列,效能不是線性搜尋的 O(n) ,而是隻有 O(log n) 。換句話說,對具有1,000,000個元素的陣列進行二分搜尋只需要大約20個步驟來查詢要查詢的內容,因為 log_2(1,000,000)= 19.9
。對於具有十億個元素的陣列,它只需要30步。 (然而,你上一次使用數十億項的陣列是什麼時候?)
聽起來很棒,但使用二分搜尋有一個缺點:陣列必須被排好序的。 在實踐中,這通常不是問題。
下面二分搜尋的工作原理:
- 將陣列分成兩半,並確定您要查詢的內容(稱為 搜尋鍵 )是在左半部分還是在右半部分。
- 您如何確定 搜尋鍵 的鍵在哪一半呢? 這就是首先要對陣列進行排序的原因,排好序你就可以做一個簡單的
<
或>
比較。 - 如果 搜尋鍵 位於左半部分,則在那裡重複該過程:將左半部分分成兩個更小的部分,並檢視 搜尋鍵 位於哪一塊。 (同樣,對於右半部分同樣處理。)
- 重複此操作直到找到 搜尋鍵 。 如果無法進一步拆分陣列,則必須遺憾地得出結論, 搜尋鍵 不在陣列中。
現在你知道為什麼它被稱為“二分”搜尋:在每一步中它將陣列分成兩半。 分而治之 可以快速縮小 搜尋鍵 所在的位置。
程式碼
這是Swift中二分搜尋的遞迴實現:
func binarySearch<T: Comparable>(_a: [T], key: T, range: Range<Int>) -> Int? { if range.lowerBound >= range.upperBound { // If we get here, then the search key is not present in the array. return nil } else { // Calculate where to split the array. let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2 // Is the search key in the left half? if a[midIndex] > key { return binarySearch(a, key: key, range: range.lowerBound ..< midIndex) // Is the search key in the right half? } else if a[midIndex] < key { return binarySearch(a, key: key, range: midIndex + 1 ..< range.upperBound) // If we get here, then we've found the search key! } else { return midIndex } } }
嘗試一下,將程式碼複製到 playground 並執行以下操作:
let numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67] binarySearch(numbers, key: 43, range: 0 ..< numbers.count)// gives 13
請注意, numbers
陣列已排序。 否則二分搜尋演算法不能工作!
二分搜尋通過將陣列分成兩半來搜尋,但我們實際上並沒有建立兩個新陣列。 我們使用Swift Range
物件跟蹤這些拆分。起初,此範圍涵蓋整個陣列, 0 .. <numbers.count
。 當我們拆分陣列時,範圍變得越來越小。
注意:需要注意的一點是 range.upperBound
總是指向最後一個元素之後的元素。 在這個例子中,範圍是 0 .. <19
,因為陣列中有19個數字,所以 range.lowerBound = 0
和 range.upperBound = 19
。但是在我們的陣列中,最後一個元素是在索引18而不是19,因為我們從0開始計數。在處理範圍時要記住這一點: upperBound
總是比最後一個元素的索引多一。
分步執行示例
檢視演算法的詳細工作方式或許是很有用的。
上例中的陣列由19個數字組成,排序後如下所示:
[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67 ]
我們試圖確定數字 43
是否在這個陣列中。
將陣列拆分為一半,我們需要知道中間物件的索引。 這是由這行程式碼確定:
let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2
最初,範圍有 lowerBound = 0
和 upperBound = 19
。 細看,我們發現 midIndex
是 0 +(19 - 0)/ 2 = 19/2 = 9
。 它實際上是 9.5
,但因為我們使用的是整數,所以答案是向下舍入了。
在下圖中, *
處表示中間項。 如您所見,每側的專案數相同,因此我們將在中間分開。
[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67 ] *
二分搜尋將確定使用哪一半的相關程式碼是:
if a[midIndex] > key { // use left half } else if a[midIndex] < key { // use right half } else { return midIndex }
在這種情況下, a[midIndex] = 29
。 這比 搜尋鍵 的值小,所以我們可以得出結論, 搜尋鍵 永遠不會出現在陣列的左半部分。畢竟,左半部分只包含小於 29
的數字。 因此, 搜尋鍵 肯定位於右半部分(或根本不在陣列中)。
現在我們可以簡單地重複二分搜尋,陣列間距從 midIndex + 1
到 range.upperBound
:
[ x, x, x, x, x, x, x, x, x, x | 31, 37, 41, 43, 47, 53, 59, 61, 67 ]
由於我們不再需要關注陣列的左半部分,我用 x
標記了它。 從現在開始,我們只看右半部分,從陣列索引10開始。
我們計算新的中間元素的索引: midIndex = 10 +(19 - 10)/ 2 = 14
,然後再將陣列從中間拆分。
[ x, x, x, x, x, x, x, x, x, x | 31, 37, 41, 43, 47, 53, 59, 61, 67 ] *
正如你所看到的, a [14]
是陣列右半部分的中間元素。
搜尋鍵 是大於還是小於 a [14]
? 小,因為 43 <47
。 這次我們取左半邊並忽略右邊較大的數字:
[ x, x, x, x, x, x, x, x, x, x | 31, 37, 41, 43 | x, x, x, x, x ]
新的 midIndex
如下:
[ x, x, x, x, x, x, x, x, x, x | 31, 37, 41, 43 | x, x, x, x, x ] *
搜尋鍵 大於 37
,因此繼續右側:
[ x, x, x, x, x, x, x, x, x, x | x, x | 41, 43 | x, x, x, x, x ] *
同樣, 搜尋鍵 更大,因此再次拆分並採取右側:
[ x, x, x, x, x, x, x, x, x, x | x, x | x | 43 | x, x, x, x, x ] *
現在我們已經完成了。搜尋鍵等於我們正在檢視的陣列元素,所以我們終於找到了我們要搜尋的內容:數字 43
位於陣列索引 13
。
這可能看起來像很多工作,但實際上只需要四個步驟就能找到陣列中的 搜尋鍵 ,因為 log_2(19)= 4.23
。通過線性搜尋,它將花費14個步驟。
如果我們要搜尋 42
而不是 43
會發生什麼?在這種情況下,最後我們不能再進一步拆分陣列。 range.upperBound
變得小於 range.lowerBound
。這告訴演算法搜尋鍵不在陣列中,它返回 nil
。
注意:二分搜尋許多執行會計算 midIndex = (lowerBound + upperBound) / 2
。這包含了一個在非常大的陣列中會出現的細微bug,因為 lowerBound + upperBound
可能溢位一個整數可以容納的最大數。這種情況不太可能發生在64位CPU上,但絕對可能在32位機器上發生。
迭代與遞迴
二分搜尋本質上是遞迴的,因為您將相同的邏輯一遍又一遍地應用於越來越小的子陣列。 但是,這並不意味著您必須將 binarySearch()
實現為遞迴函式。 將遞迴演算法轉換為迭代版本通常更有效,使用簡單的迴圈而不是大量的遞迴函式呼叫。
這是Swift中二分搜尋的迭代實現:
func binarySearch<T: Comparable>(_a: [T], key: T) -> Int? { var lowerBound = 0 var upperBound = a.count while lowerBound < upperBound { let midIndex = lowerBound + (upperBound - lowerBound) / 2 if a[midIndex] == key { return midIndex } else if a[midIndex] < key { lowerBound = midIndex + 1 } else { upperBound = midIndex } } return nil }
如您所見,程式碼與遞迴版本非常相似。 主要區別在於使用 while
迴圈。
使用迭代實現:
let numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67] binarySearch(numbers, key: 43)// gives 13
結束
陣列必須先排序是一個問題? 排序是需要時間的 —— 二分搜尋和排序的組合可能比進行簡單的線性搜尋要慢。但是在您只排序一次然後進行多次搜尋的情況下,二分搜尋會起到大作用。
作者:Matthijs Hollemans
翻譯: Andy Ron
校對: Andy Ron