swift - 在 Swift 中以前提条件获取子序列的有效方法

Question

我有一个有序的数字序列，让我们说一下

0, 1, 2, 3, 5, 6, 11, 12, 15, 20

给定一个数字 N，我怎么能得到一个从最后一个小于 N 的数字开始的序列？例如，如果 N = 7，我想回来

6, 11, 12, 15, 20

请注意，这个序列会变得非常大，并且会附加新的数字。 drop(while:)看起来是一个不错的候选，但在上面的例子中它也会下降 6所以我不能使用它。

Answer 1

对于巨大的已排序 数组最有效的方法是二分查找。它将数组切成两半，直到找到索引。

extension RandomAccessCollection where Element : Comparable {
    func lastIndex(before value: Element) -> Index {
        var slice : SubSequence = self[...]

        while !slice.isEmpty {
            let middle = slice.index(slice.startIndex, offsetBy: slice.count / 2)
            if value < slice[middle] {
                slice = slice[..<middle]
            } else {
                slice = slice[index(after: middle)...]
            }
        }
        return slice.startIndex == self.startIndex ? startIndex : index(before: slice.startIndex)
    }
}

let array = [0, 1, 2, 3, 5, 6, 11, 12, 15, 20]
let index = array.lastIndex(before: 7)
print(array[index...])