我有一个排序数组,想对其进行二分搜索。
所以我问 Swift 库中是否已经有一些东西可以使用,比如排序等?或者是否有可用的类型无关版本?
当然我可以自己写,但我喜欢避免再次重新发明轮子。
这是我最喜欢的二分搜索实现。它不仅对于查找元素很有用,而且对于查找插入索引也很有用。有关假定的排序顺序(升序或降序)和相等元素的行为的详细信息通过提供相应的谓词(例如{ $0 < x }
vs { $0 > x }
vs { $0 <= x }
vs { $0 >= x }
)。该评论明确说明了它到底是做什么的。
extension RandomAccessCollection {
/// Finds such index N that predicate is true for all elements up to
/// but not including the index N, and is false for all elements
/// starting with index N.
/// Behavior is undefined if there is no such N.
func binarySearch(predicate: (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
}
}
用法示例:
(0 ..< 778).binarySearch { $0 < 145 } // 145
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)