arrays - Swift:二进制搜索标准数组？

Question

我有一个排序数组，想对其进行二分查找。

所以我想问一下 Swift 库中是否已经提供了一些东西，比如 sort 等？或者是否有可用的类型独立版本？

我当然可以自己写，但我想避免重新造轮子。

Answer 1

这是我最喜欢的二分搜索实现。它不仅对查找元素很有用，而且对查找插入索引也很有用。通过提供相应的谓词(例如 { $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