可街协议

Question

我正在尝试转换以下Swift 2.3代码：

//Example usage:
//(0 ..< 778).binarySearch { $0 < 145 } // 145
extension CollectionType where Index: RandomAccessIndexType {

    /// 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: Generator.Element -> Bool)
        -> Index {
        var low = startIndex
        var high = endIndex
        while low != high {
            let mid = low.advancedBy(low.distanceTo(high) / 2)
            if predicate(self[mid]) {
                low = mid.advancedBy(1)
            } else {
                high = mid
            }
        }
        return low
    }
}

进入Swift 3，如下所示：

//Example usage:
//(0 ..< 778).binarySearch { $0 < 145 } // 145
extension Collection where Index: Strideable {

    /// 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: (Generator.Element) -> Bool)
        -> Index {
        var low = startIndex
        var high = endIndex
        while low != high {
            let mid = low.advanced(by: low.distance(to: high) / 2)
            if predicate(self[mid]) {
                low = mid.advanced(to: 1)
            } else {
                high = mid
            }
        }
        return low
    }
}

错误

二进制运算符'/'不能应用于类型'self.Index.Stride'和'Int'的操作数

被扔在 let mid = low.advanced(by: low.distance(to: high) / 2)

对如何修复有帮助吗？

Answer 1

在Swift 3中，“集合移动其索引”，比较了 关于Swift进化的集合和索引的新模型。特别是，您不会调用advancedBy()索引，而是调用index()集合上的一种方法来推进索引。

因此，您的方法将在Swift 3中实现为

extension RandomAccessCollection {

    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
    }
}

同样的方法也可以作为更通用Collection类型的扩展进行编译（和工作），但是-正如瓦迪姆·叶拉金（Vadim Yelagin）正确指出的那样，如果无法在恒定时间内完成索引/偏移量计算，效率将非常低下。