swift - 扩展哪个 Swift 集合协议(protocol)以添加二进制搜索

Question

我想实现一些类似于二进制搜索的函数，这些函数对可随机访问(在恒定时间内)并支持索引算法(用于导出中点)的已排序元素集合进行操作。我可以将这些方法添加为扩展或 Array。但是，我更愿意将它们添加到支持必要功能的更通用的协议(protocol)中，以便我的扩展可以更广泛地使用。

我应该使用哪种协议(protocol)，将来如何找到此类协议(protocol)？我搜索了“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:) .

这两种方法的文档都指出复杂度是

O(1) if the collection conforms to RandomAccessCollection; otherwise, O(n), where n is the absolute value of n.

所以你可以将它实现为 RandomAccessCollection 的扩展如果你想保证它只用于移动索引和测量距离是 O(1) 操作。

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