要扩展哪种Swift收集协议以添加二进制搜索

Question

我想实现一些二进制搜索，比如对可随机访问(在固定时间内)的有序元素集合进行操作的函数，并且支持索引算法(用于导出中间点)。我可以将这些方法作为扩展或Array添加。但是，我更喜欢将它们添加到支持必要功能的更通用的协议中，这样我的扩展就可以得到更广泛的使用。

我应该使用哪种协议，以及将来如何查找这样的协议？我搜索了"Swift collection protocol hierarchy“和类似的内容，除了各种转移注意力的问题之外，我没有找到任何有用的东西。

Answer 1

对于二进制搜索，您需要找到两个索引位置之间的“中点”，这对于任何Collection都是可能的，因为它关联的IndexDistance必须是SignedInteger。

一种可能的实现(取自https://stackoverflow.com/a/40226976/1187415)是

extension Collection {

    func binarySearch(predicate: (Iterator.Element) -> Bool) -> Index {
        var low = startIndex
        var high = endIndex
        while low != high {
            let mid = index(low, offsetBy: distance(from: low, to: high)/2)
            if predicate(self[mid]) {
                low = index(after: mid)
            } else {
                high = mid
            }
        }
        return low
    }
}

这里distance(from:to:)返回一个可以被2整除的IndexDistance，因为它符合SignedInteger (因此也符合IntegerArithmetic)，结果可以在index(_:offsetBy:)中使用。

这两种方法的文档都说明了复杂性是

如果集合符合RandomAccessCollection，则返回O(1)；否则为O( n )，其中n是n的绝对值。

因此，如果您希望保证它仅用于移动索引和测量距离是O(1)操作的集合，则可以将其实现为RandomAccessCollection的扩展。

或者您将其实现为Collection的扩展，这样它就可以被普遍使用。当在RandomAccessCollection上调用时，它将是“快”的(在上面的意义上)，否则可能是“慢”的。