声明：算法和数据结构的文章均是作者从github上翻译过来，为方便大家阅读。如果英语阅读能力强的朋友，可以直接到swift算法俱乐部查看所有原文，以便快速学习。作者同时也在学习中，欢迎交流
目的：快速找到数组中的某一元素。
假如你有一个数组，包含数百个数字，然后你需要从中找出某一个数字所在的位置，在大多数情况下，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
Swift自带的 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
虽然很简便，但是由于是线性搜索，意味着我们需要从数组的第一位开始搜索整个数组，在最糟糕的情况下，可能你需要搜寻完整个数组才发现数组里面没有你需要寻找的数字。所以说，线性搜索算法跟数组的大小相关性很大，数组越大，意味着消耗的时间越久。
分治法
对于数组大的情况下，最经典的算法当属二分搜索算法。它的核心就是不断的将数组一分为二，直到找到我们寻找的数字。
比如说，一个大小为n的数组，使用线性搜索算法的效率为O(n)，而二分搜索算法的效率为O(log n)。更详细一点来说，当数组大小为1000000的时候，二分搜索算法只花了20步就能找到结果。因为log_2(1000000) = 19.9。而当数组大小上升到十亿级别的时候，二分搜索却只需要30步就能找到答案。
不过，使用二分搜索必须有个前提：这个必须数组是按照一定顺序排列的。
二分搜索的工作原理：
1.将数组一分为二，并决定你需要寻找的元素是在数组的左边还是右边。
2.由于我们的数组是已经排序好的数组，所以你只需要将寻找的元素和得到中间数字进行大小比较。
3.确定好寻找的元素在哪边后，在新的数组里面继续一分为二，然后比较大小。
4.不断重复上述过程，直到我们找到这个元素在数组中的位置，或者当数组无法继续一分为二的时候，判断数组中不存在需要寻找的元素。
代码
以下为递归版的二分搜索算法：
func binarySearch<T: Comparable>(_ a: [T], key: T, range: Range<Int>) -> Int? {
if range.lowerBound >= range.upperBound {
// 如果我们进入这个函数，则说明要寻找的元素不在数组里
return nil
} else {
// 计算数组一分为二的位置
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)
// 如果进入这个函数内部，则说明我们已经在数组里找到这个元素！
} 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) // 得到 13
必须注意这里的numbers是已经排序好的！
虽然说二分算法是不断的进行数组拆分，但是这里我们并不是真的去创建两个新的数组，而是使用Swfit中的Range对象。最初的时候，range包含数组的所有元素的位置，0..<numbers.count，随着拆分不断进行，range越变越小。
示例解析
我们有一组已经排序好的数组：
[ 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 = 9.5 = 9（向下取整）。如图，我们的中间数组为29，其左右两个数组位数大小相等。
[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67 ]
*
接下来，二分算法将会决定我们接下去会使用哪一边的数组。相关代码为：
if a[midIndex] > key {
// 使用左边部分
} else if a[midIndex] < key {
// 使用右边部分
} else {
return midIndex
}
由于29比43小，所以我们可以确定左侧的数组不存在43。我们继续在右侧数组中寻找43。此时新的范围为midIndex + 1 到range.upperBound。
[ x, x, x, x, x, x, x, x, x, x | 31, 37, 41, 43, 47, 53, 59, 61, 67 ]
此时新的中间值为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 ]
*
新的中间值对应的数字为47<43，所以我们继续在左侧数组进行拆分。
[ x, x, x, x, x, x, x, x, x, x | 31, 37, 41, 43 | x, x, x, x, x ]
此时新的中间值为：
[ x, x, x, x, x, x, x, x, x, x | 31, 37, 41, 43 | x, x, x, x, x ]
*
37<43。在右侧数组继续拆分：
[ x, x, x, x, x, x, x, x, x, x | x, x | 41, 43 | x, x, x, x, x ]
*
再一次，41<43，继续拆分：
[ x, x, x, x, x, x, x, x, x, x | x, x | x | 43 | x, x, x, x, x ]
*
终于，我们找到了43，此时的中间值为13，即43在数组的位置为13。整个过程看起来好像很冗长，但其实我们只花了4个步骤就得到了答案。与log_2(19) = 4.23相近。而如果是线性搜索，我们需要花14个步骤才能找到43！
迭代vs递归
通常情况下二分搜索属于递归过程，因为不断运用了同样的逻辑去缩小数组。但是这不意味着我们不能使用迭代的方法去实现二分搜索。同时，递归算法转化成迭代算法实现通常会提高运行效率，因为它只用了一个循环而不是多个嵌套循环。
以下为迭代版本的二分搜索算法：
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循环的使用。我们同样可以在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) // 得到13
结语
看到这里，是否会感觉需要将数组先进行排序会很复杂？其实不然，虽然排序也需要花时间，但是，排序加上二分搜索的过程往往会比直接进行线性查找来得更快速。 特别是当你不是单单只想寻找一个元素的情况下。
