二分搜索（英语：binary search），也称折半搜索（英语：half-interval search）、对数搜索（英语：logarithmic 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 {
// 如果执行这里，说明搜索键不在数组中
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)
注意，数字数组必须是排序的。否则二分搜索算法不能工作！
我们说二分搜索的工作原理是将数组分成两半，但实际上不需要创建两个新的数组。 相反，我们使用 Swift Range 对象来跟踪拆分的位置。 最初，此范围覆盖整个数组，从 0 .. <numbers.count。 当我们拆分数组时，范围变得越来越小。
注意：需要注意的一点是，
range.upperBound的值总是会比最后一个索引大。 在示例中，范围是0 .. <19，因为在数组中有19个数字，因此range.lowerBound = 0，range.upperBound = 19。但在我们的数组中，最后一个元素是在索引18，而不是19， 因为我们从0开始计数。
逐步分析实例
详细看看算法如何工作是很有用的。
上面的示例中的数组由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 {
// 使用左半部分
} else if a[midIndex] < key {
// 使用右半部分
} 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。这包含一个只有非常大的数组才出现的微妙错误，因为lowerBound + upperBound可能溢出整数范围。这种情况不太可能发生在64位CPU上，但它可能发生在32位CPU上。
迭代与递归
二分搜索本质上是递归的，因为将相同的逻辑一遍又一遍地应用于越来越小的分割后的数组。然而，这并不意味着你必须用递归的方式实现 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 -- Swift算法俱乐部
英文链接：
https://github.com/raywenderlich/swift-algorithm-club/tree/master/Binary%20Search
网友评论