20.二进制搜索¶

二进制搜索是最有效的搜索算法之一，其时间复杂度为O(log n)。这与在一个 "平衡 "的二进制搜索树内搜索一个元素相媲美。

在使用二进制搜索之前，需要满足两个条件。

集合必须能够在恒定时间内执行索引操作。这意味着该集合必须是一个RandomAccessCollection。
集合必须是sorted。

示例¶

二进制搜索的好处最好通过与线性搜索相比较来说明。Swift的Array类型使用线性搜索来实现其firstIndex(of:)方法。它遍历整个集合或直到找到第一个元素：

二进制搜索的处理方式不同，它利用了集合已经被排序的事实。

下面是一个应用二进制搜索来寻找数值31的例子：

与其说找到31个步骤，不如说只需要三个步骤。下面是它的工作原理：

第1步：查找中间索引¶

第一步是找到集合的中间索引。找到它是相当简单的：

第2步：检查中间索引的元素¶

下一步是检查存储在中间索引的元素。如果它与你要找的值相匹配，返回索引。否则，继续进行第3步。

第3步：递归调用二进制搜索¶

最后一步是递归地调用二进制搜索。然而，这一次，你将只考虑中间索引的left或right的元素，这取决于你要搜索的值。如果你要搜索的值小于中间值，你就搜索左边的子序列。如果它大于中间值，你就搜索右边的子序列。

每一步都有效地消除了你需要进行的一半的比较。

在这个例子中，你要寻找的值是31（大于中间的元素22），你在右边的子序列上应用二进制搜索：

你继续这三个步骤，直到你不能再把集合分成左右两半，或者直到你找到集合里面的值。

二进制搜索以这种方式实现了O(log n)的时间复杂性。

实施¶

打开本章的启动程序。在Sources文件夹中创建一个新的文件，名为BinarySearch.swift。在该文件中添加以下内容：

// 1
public extension RandomAccessCollection where Element: Comparable {
  // 2
  func binarySearch(for value: Element, in range: Range<Index>? = nil)
      -> Index? {
    // more to come
  }
}

到目前为止，事情还比较简单：

由于二进制搜索只适用于符合RandomAccessCollection的类型，你在RandomAccessCollection的扩展中添加该方法。这个扩展是有限制的，因为你需要能够比较元素。
二进制搜索是递归的，所以你需要传入一个范围来搜索。参数range是可选的，所以你可以不指定一个范围就开始搜索。在这种情况下，如果range是nil，整个集合都会被搜索到。

接下来，实现binarySearch，如下所示：

// 1
let range = range ?? startIndex..<endIndex
// 2
guard range.lowerBound < range.upperBound else {
  return nil
}
// 3
let size = distance(from: range.lowerBound, to: range.upperBound)
let middle = index(range.lowerBound, offsetBy: size / 2)
// 4
if self[middle] == value {
  return middle
// 5
} else if self[middle] > value {
  return binarySearch(for: value, in: range.lowerBound..<middle)
} else {
  return binarySearch(for: value, in: index(after: middle)..<range.upperBound)
}

以下是有关步骤：

首先，你检查range是否为nil。如果是，你就创建一个涵盖整个集合的范围。
然后，你检查这个范围是否包含至少一个元素。如果不包含，则搜索失败，并返回nil。
现在你确定你的范围内有元素，你找到范围内的中间索引。
然后将这个索引的值与你要搜索的值进行比较。如果数值匹配，你就返回中间的索引。
如果不匹配，你就递归地搜索集合的左半部分或右半部分。

这样就完成了二进制搜索的实现! 回到操场页面来测试一下。在操场页面的顶部写下以下内容：

let array = [1, 5, 15, 17, 19, 22, 24, 31, 105, 150]

let search31 = array.firstIndex(of: 31)
let binarySearch31 = array.binarySearch(for: 31)

print("firstIndex(of:): \(String(describing: search31))")
print("binarySearch(for:): \(String(describing: binarySearch31))")

你应该在控制台看到以下输出：

index(of:): Optional(7)
binarySearch(for:): Optional(7)

这是你要找的值的索引。

二进制搜索是一种强大的学习算法，在编程面试中经常出现。每当你读到"给定一个排序的数组..."这样的内容时，考虑使用二进制搜索算法。另外，如果你得到的问题看起来要用O(n²)来搜索，考虑做一些前期的排序，这样你就可以用二进制搜索把它减少到O(n log n)的排序成本。

关键点¶

二进制搜索只在sorted的集合上是一种有效的算法。
有时，对一个集合进行排序以利用二进制搜索的能力来查找元素可能是有益的。
序列上的firstIndex(of:)方法使用线性搜索，有O(n)时间复杂度。二进制搜索有O(log n)的时间复杂度，如果你在做重复的查找，对于大数据集来说，它的扩展性更好。