二分搜索（英語(yǔ)：binary search）挥唠，也稱折半搜索（英語(yǔ)：half-interval search）、對(duì)數(shù)搜索（英語(yǔ)：logarithmic search) 纲菌。
目標(biāo)：快速找到數(shù)組中的元素挠日。
假設(shè)你有一個(gè)數(shù)字?jǐn)?shù)組，你想確定一個(gè)特定的數(shù)字是否在該數(shù)組翰舌，如果在嚣潜，索引是多少。
在大多數(shù)情況下椅贱，Swift 內(nèi)置的 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
內(nèi)置的線性搜索函數(shù) indexOf() 懂算，大概是這樣實(shí)現(xiàn)的：
func linearSearch<T: Equatable>(_ a: [T], _ key: T) -> Int? {
for i in 0 ..< a.count {
if a[i] == key {
return i
}
}
return nil
}
你會(huì)這樣使用它：
linearSearch(numbers, 43) // returns 15
那么問(wèn)題是什么？ linearSearch() 從頭開(kāi)始遍歷整個(gè)數(shù)組庇麦，直到找到您要查找的元素计技。 在最壞的情況下，數(shù)組中沒(méi)有要查找的元素山橄，所有的工作都白白浪費(fèi)了垮媒。
根據(jù)平均水平來(lái)說(shuō)，線性搜索算法需要查看數(shù)組中的一半的元素航棱。 如果你的數(shù)組足夠大睡雇，這會(huì)變得非常慢！
分而治之
加快速度的經(jīng)典方法是使用二分搜索饮醇。 訣竅是將數(shù)組分成兩半入桂，直到找到值。
對(duì)于大小為n的數(shù)組驳阎，性能不像線性搜索那樣是 O(n) 木柬，而是只有 O(log n) 。舉例來(lái)說(shuō)用僧，對(duì)具有1,000,000個(gè)元素的數(shù)組的二進(jìn)制搜索只需要大約20個(gè)步驟來(lái)找到你想要的必盖，因?yàn)?log_2(1,000,000) = 19.9 。 對(duì)于一個(gè)擁有十億個(gè)元素的數(shù)組饵隙，它只需要30個(gè)步驟撮珠。 （想想看，最后一次你使十億個(gè)元素的數(shù)組是什么時(shí)候金矛？）
聽(tīng)起來(lái)不錯(cuò)芯急，但使用二分搜索有一個(gè)缺點(diǎn)：數(shù)組必須排序勺届。 在實(shí)踐中，這通常不是問(wèn)題娶耍。
下面是二分搜索的工作原理：
將數(shù)組分成兩半免姿，并確定您要查找的內(nèi)容（稱為搜索鍵）是位于左半邊還是右半邊。
如何確定搜索哪一半榕酒？ 這就是為什么你首先要將數(shù)組排序胚膊，所以你可以做一個(gè)簡(jiǎn)單的
<或>比較。如果搜索鍵在左半部分想鹰，您可以重復(fù)此處的過(guò)程：將左半部分分成兩個(gè)更小的部分紊婉，并查找搜索鍵必須位于哪個(gè)部分。 (右半邊同理)
這一過(guò)程不斷重復(fù)辑舷，直到搜索鍵被發(fā)現(xiàn)喻犁。 如果數(shù)組不能被進(jìn)一步拆分，則必須遺憾地得出結(jié)論：搜索鍵不存在于數(shù)組中何缓。
現(xiàn)在你知道為什么它被稱為“二分”搜索：在每一步株汉，它將數(shù)組分成兩半。 這種分而治之的過(guò)程通過(guò)搜索鍵快速縮小搜索范圍歌殃。
代碼
這是一個(gè)遞歸實(shí)現(xiàn)二分搜索的 Swift 代碼：
func binarySearch<T: Comparable>(_ a: [T], key: T, range: Range<Int>) -> Int? {
if range.lowerBound >= range.upperBound {
// 如果執(zhí)行這里乔妈，說(shuō)明搜索鍵不在數(shù)組中
return nil
} else {
// 計(jì)算出在哪里數(shù)組拆分
let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2
// 搜索鍵是在左半邊嗎？
if a[midIndex] > key {
return binarySearch(a, key: key, range: range.lowerBound ..< midIndex)
// 搜索鍵是在右半邊嗎氓皱？
} else if a[midIndex] < key {
return binarySearch(a, key: key, range: midIndex + 1 ..< range.upperBound)
// 如果執(zhí)行這里路召，那么我們找到了搜索鍵！
} else {
return midIndex
}
}
}
把這段代碼放到 playground 里并測(cè)試：
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)
注意波材，數(shù)字?jǐn)?shù)組必須是排序的股淡。否則二分搜索算法不能工作！
我們說(shuō)二分搜索的工作原理是將數(shù)組分成兩半廷区，但實(shí)際上不需要?jiǎng)?chuàng)建兩個(gè)新的數(shù)組唯灵。 相反，我們使用 Swift Range 對(duì)象來(lái)跟蹤拆分的位置隙轻。 最初埠帕，此范圍覆蓋整個(gè)數(shù)組，從 0 .. <numbers.count玖绿。 當(dāng)我們拆分?jǐn)?shù)組時(shí)敛瓷，范圍變得越來(lái)越小。
注意：需要注意的一點(diǎn)是斑匪，
range.upperBound的值總是會(huì)比最后一個(gè)索引大呐籽。 在示例中，范圍是0 .. <19，因?yàn)樵跀?shù)組中有19個(gè)數(shù)字狡蝶，因此range.lowerBound = 0庶橱，range.upperBound = 19。但在我們的數(shù)組中贪惹，最后一個(gè)元素是在索引18苏章，而不是19， 因?yàn)槲覀儚?開(kāi)始計(jì)數(shù)馍乙。
逐步分析實(shí)例
詳細(xì)看看算法如何工作是很有用的。
上面的示例中的數(shù)組由19個(gè)數(shù)字組成垫释，排序后顯示如下：
[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67 ]
我們?cè)噲D確定數(shù)字43是否在這個(gè)數(shù)組中丝格。
將數(shù)組分成兩半，我們需要知道中間對(duì)象的索引棵譬。 對(duì)應(yīng)這一行：
let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2
最初显蝌，范圍是 lowerBound = 0 到 upperBound = 19。帶入這些值订咸，我們發(fā)現(xiàn) midIndex 是 0 + (19 - 0)/2 = 19/2 = 9曼尊。實(shí)際上是9.5，但因?yàn)槲覀兪褂谜麛?shù)脏嚷，向下舍入骆撇。
在下圖中，* 表示中間項(xiàng)目父叙。 正如你所看到的神郊，每一側(cè)的項(xiàng)目數(shù)量是相同的，所以我們是在中間分割趾唱。
[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67 ]
*
現(xiàn)在二分搜索將確定使用哪一半涌乳。 對(duì)應(yīng)的代碼中是：
if a[midIndex] > key {
// 使用左半部分
} else if a[midIndex] < key {
// 使用右半部分
} else {
return midIndex
}
在這種情況下， a[midIndex] = 29 甜癞。它小于搜索鍵夕晓，因此我們百分百可以斷定搜索鍵永遠(yuǎn)不會(huì)在數(shù)組的左半部分。畢竟悠咱，左半部分只包含小于29的數(shù)字蒸辆。因此，搜索鍵必須在右半部分（或根本不在數(shù)組中）析既。
現(xiàn)在我們可以簡(jiǎn)單地重復(fù)二分搜索吁朦，但在數(shù)組間隔從 midIndex + 1 到 range.upperBound：
[ x, x, x, x, x, x, x, x, x, x | 31, 37, 41, 43, 47, 53, 59, 61, 67 ]
因?yàn)槲覀儾辉傩枰P(guān)心數(shù)組的左半部分，所以我用 x 的標(biāo)記它們渡贾。 從現(xiàn)在開(kāi)始逗宜，我們只看到右半部分，從數(shù)組索引10開(kāi)始。
我們計(jì)算新的中間元素的索引：midIndex = 10 + (19 - 10)/2 = 14 纺讲，并再次將數(shù)組從中間分割擂仍。
[ x, x, x, x, x, x, x, x, x, x | 31, 37, 41, 43, 47, 53, 59, 61, 67 ]
*
正如你所看到的，a[14] 確實(shí)是數(shù)組右半邊的中間元素熬甚。
搜索鍵大于還是小于 a[14] ? 搜索鍵更小逢渔，因?yàn)?43 < 47。這次我們關(guān)注左半邊乡括，忽略右半邊的數(shù)字：
[ 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, 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 ]
*
現(xiàn)在我們完成了盲赊。 搜索鍵等于我們正在查看的數(shù)組元素，所以我們終于找到了我們要搜索的：數(shù)字 43 在數(shù)組的索引是 13 敷扫。
這可能看起來(lái)像很多工作哀蘑，但在現(xiàn)實(shí)中，只需要四個(gè)步驟就能找到數(shù)組中的搜索鍵葵第，因?yàn)?log_2(19) = 4.23 绘迁。如果使用線性搜索，將需要14個(gè)步驟卒密。
如果我們要搜索 42 而不是 43 缀台，會(huì)發(fā)生什么？在這種情況下哮奇，我們不能進(jìn)一步拆分?jǐn)?shù)組将硝。 range.upperBound 小于了 range.lowerBound 。這說(shuō)明搜索鍵不在數(shù)組中屏镊，返回nil依疼。
注意：許多二叉搜索的實(shí)現(xiàn)都會(huì)這樣計(jì)算
midIndex = (lowerBound + upperBound) / 2。這包含一個(gè)只有非常大的數(shù)組才出現(xiàn)的微妙錯(cuò)誤而芥，因?yàn)?lowerBound + upperBound可能溢出整數(shù)范圍律罢。這種情況不太可能發(fā)生在64位CPU上，但它可能發(fā)生在32位CPU上棍丐。
迭代與遞歸
二分搜索本質(zhì)上是遞歸的误辑，因?yàn)閷⑾嗤倪壿嬕槐橛忠槐榈貞?yīng)用于越來(lái)越小的分割后的數(shù)組。然而歌逢，這并不意味著你必須用遞歸的方式實(shí)現(xiàn) binarySearch()方法巾钉。將遞歸算法轉(zhuǎn)換為迭代方式通常更有效，使用簡(jiǎn)單的循環(huán)秘案，而不是大量的遞歸函數(shù)調(diào)用砰苍。
這是一個(gè)用迭代實(shí)現(xiàn)的二分搜索算法的 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
}
如你所見(jiàn)潦匈，與遞歸版本的代碼非常相似。 主要區(qū)別在于使用while循環(huán)赚导。
這樣使用：
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
結(jié)束語(yǔ)
二分搜索面臨這樣一個(gè)問(wèn)題：數(shù)組必須先排序茬缩？ 請(qǐng)記住，排序需要時(shí)間 -- 二分搜索加排序的組合可能比執(zhí)行簡(jiǎn)單的線性搜索慢吼旧。 二進(jìn)制搜索閃光點(diǎn)在與只排序一次凰锡，然后進(jìn)行很多搜索的情況。
作者：Matthijs Hollemans -- Swift算法俱樂(lè)部
英文鏈接：
https://github.com/raywenderlich/swift-algorithm-club/tree/master/Binary%20Search
