第21章：二进制搜索进阶
挑战1：作为自由函数的二进制搜索
在上一章中，你实现了二进制搜索，作为RandomAccessCollection协议的一个扩展。由于二进制搜索只对有排序的集合起作用，将该函数作为RandomAccessCollection的一部分公开会有误用的可能。
你的挑战是将二进制搜索作为一个自由函数来实现。
挑战 2：搜索一个范围
编写一个函数，搜索一个已排序的数组，找到某个特定元素的索引范围。例如。
let array = [1, 2, 3, 3, 3, 4, 5, 5]
findIndices(of: 3, in: array)
findIndices应该返回2...<5的范围，因为这些是值3的开始和结束索引。
解决方案
挑战1的解决方案
在这个挑战中，你要把二进制搜索作为一个自由函数来实现。下面是这个函数的样子。
挑战2的解决方案
一个未经优化但优雅的解决方案是非常简单的。
这个解决方案的时间复杂度是O(n)，这似乎不是一个值得关注的问题。然而，这个解决方案可以被优化为一个O(_log n)时间复杂度的解决方案。
二进制搜索是一种识别排序集合中的值的算法，所以只要问题承诺是一个排序的集合，就要记住这一点。你在理论章节中实现的二进制搜索不够强大，无法推理出索引是起始索引还是结束索引。你要修改你学到的二进制搜索，以适应这一新规则。
在你的playground上写下以下内容。
这一次，findIndices将使用专门的二进制搜索。 startIndex和endIndex将是用定制的二进制搜索来完成重任。你将修改二进制搜索以检查相邻的值（取决于你寻找的是起始索引还是结束索引）是否与当前值不同。将startIndex方法更新为以下内容。
下面是你用这个代码做的事情。
-
你开始计算范围内所含指数的中间值。
-
这是这个递归函数的基本情况。如果中间索引是数组的第一个或最后一个可访问索引，你就不需要再调用二进制搜索。你将确定当前的索引是否是给定值的有效边界。
-
在这里，你检查索引处的值，并进行你的递归调用。如果midIndex处的值等于你给定的值，你就检查前身是否也是相同的值。如果不是，你就知道你已经找到了起始边界。否则，你将继续递归地调用startIndex。
endIndex方法也是类似的。将endIndex的实现更新为以下内容。
在playground的底部写下以下内容，测试一下你的解决方案。
你应该在控制台看到以下输出。
2..<5
这个函数将时间复杂度从O(n)提高到O(log n)。
| 上一章 | 目录 | 下一章 |
|---|