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...])