第20章：二进制搜索

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

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

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

• 该集合必须被排序。

例子

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

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

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

找到31不需要八个步骤，而只需要三个步骤。下面是它的工作原理。

第一步：寻找中间索引

第一步是找到集合的中间索引。找到它是相当直接的。

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

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

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

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

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

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

你继续这三个步骤，直到你不能再将集合分成左右两半，或者直到你在集合中找到了值。

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

实现

打开本章的启动器游戏场。在 Sources 文件夹中创建一个名为 BinarySearch.swift 的新文件。在该文件中添加以下内容。

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

1. 由于二进制搜索只适用于符合RandomAccessCollection的类型，所以你在RandomAccessCollection的扩展中添加该方法。这个扩展是有限制的，因为你需要能够对元素进行比较。

2. 二进制搜索是递归的，所以你需要传入一个范围来搜索。参数range是可选的，所以你可以不指定一个范围就开始搜索。在这种情况下，如果range为nil，整个集合将被搜索。接下来，实现 binarySearch，如下所示。

下面是步骤。

1. 首先，你检查range是否是nil。如果是，你就创建一个覆盖整个集合的范围。

2. 然后，检查这个范围是否至少包含一个元素。如果没有，则搜索失败，返回nil。

3. 现在你确定你的范围内有元素，你找到范围内的中间索引。

4. 然后将这个索引的值与你要搜索的值进行比较。如果数值匹配，你就返回中间的索引。

5. 如果不匹配，你就递归地搜索集合的左半部分或右半部分。

二进制搜索的实现就这样结束了! 回到playground页面来测试它。在playground页面的顶部写下以下内容。

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

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

这是你要找的值的索引。

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

关键点

• 二进制搜索只在排序的集合上是一种有效的算法。

• 有时，对一个集合进行排序以利用二进制搜索功能来查找元素可能是有益的。

• 序列上的firstIndex(of:)方法使用线性搜索，其时间复杂度为O(n)。二进制搜索的时间复杂度为O(log n)，如果你要进行重复查找，对于大数据集来说，二进制搜索的扩展性要好很多。

---

上一章	目录	下一章