Efficient way to get a subsequence with a precondition in Swift

user_289501 0
Viewed 97

I have an ordered sequence of numbers, let's say something like

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

Given a number N, how could I get a sequence that starts from the last number that is smaller than N? For example, if N = 7, I'd like to get back

6, 11, 12, 15, 20

Please note that this sequence will get very big and new numbers will be appended.

drop(while:) seemed like a good candidate, but in the example above it would also drop 6 so I can't use it.

swift data-structures algorithm
1 Answers

For huge sorted arrays the most efficient way is binary search. It cuts the array in half until the index was found.

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