我想实现一些类似于二进制搜索的函数,这些函数对可随机访问(在恒定时间内)并支持索引算法(用于导出中点)的已排序元素集合进行操作。我可以将这些方法添加为扩展或 Array
。但是,我更愿意将它们添加到支持必要功能的更通用的协议(protocol)中,以便我的扩展可以更广泛地使用。
我应该使用哪种协议(protocol),将来如何找到此类协议(protocol)?我搜索了“Swift collection protocol hierarchy”和类似的东西,但除了各种转移注意力之外,我没有发现任何有用的东西。
最佳答案
对于二进制搜索,您需要找到两个之间的“中点”
索引位置,这对于任何 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
上调用,否则可能会“慢”。
关于swift - 扩展哪个 Swift 集合协议(protocol)以添加二进制搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44291405/