Swift: Fast way to increment part of an integer array

I have an array of increasing integers like so: [0, 5, 23, …]. The array is big (> 500T). I have to find all elements larger than an input value x and add 1 to each of them.

I do the following:

extension Array where Element == Int {
    func incrementElements(largerThan x: Int) -> [Int] {
        return self.map { $0 > x ? $0 + 1 : $0 }
    }
}

So far so good. The problem is that this operation must be very fast and mine is too slow. Is there a faster way to do this?

You are testing every single element in the array ("is this element larger than x? okay, is this element larger than x? Okay, what about this element...?"). That's silly. If the array is sorted to begin with ("an array of increasing integers"), you already know that you only need to increment the elements after the last "smaller than or equal to x" element.

Thus it is necessary to traverse the array at most once, and it is only necessary to do any testing long enough to find the first element that is greater than x.

We can traverse the array most efficiently by pointing directly into its contiguous buffer storage. So our traversal might look like this:

// initial conditions
var array = [1, 2, 3, 4, 5, 6, 7] // or whatever
let k = 3 // or whatever; this is your `x`

// okay, here we go
array.withUnsafeMutableBufferPointer { buffer in
    var index: Int?
    for i in (buffer.startIndex..<buffer.endIndex) {
        if buffer[i] > k {
            index = i
            break
        }
    }
    if let index {
        for i in (index..<buffer.endIndex) {
            buffer[i] += 1
        }
    }
}

We could make this even faster by eliminating the first part of the traversal; instead, we could use a binary search to locate the first element that is greater than x. But this is left as an exercise for the reader.