时间戳

首页 > 解决方案 > 在 Swift 中获取具有前提条件的子序列的有效方法

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

问题描述

我有一个有序的数字序列，比如说

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

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

6, 11, 12, 15, 20

请注意，这个序列会变得非常大，并且会附加新的数字。

drop(while:)似乎是一个不错的候选人，但在上面的例子中它也会下降6，所以我不能使用它。

标签： swiftalgorithmdata-structures

解决方案

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

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

推荐阅读