arrays - 如何在正确的位置将元素插入 Swift 中的排序数组？

Question

NSArray 有 - (NSUInteger)indexOfObject:(id)obj inSortedRange:(NSRange)r options:(NSBinarySearchingOptions)opts usingComparator:(NSComparator)cmp 来确定在排序数组中插入新对象的位置。

在纯 Swift 中执行此操作的最佳和高性能方法是什么？

类似的东西:

var myArray = ["b", "e", "d", "a"]
myArray.sort { $0 < $1 }

// myArray is now [a, b, d, e]

myArray.append("c")
myArray.sort { $0 < $1 }

// myArray is now [a, b, c, d, e]

我不想附加新元素然后对数组进行排序，而是想找出正确的位置并插入元素:

let index = [... how to calculate this index ??? ...]
myArray.insert("c", atIndex: index)

Answer 1

这里是 Swift 中使用二进制搜索的可能实现(来自 http://rosettacode.org/wiki/Binary_search#Swift稍作修改):

extension Array {
    func insertionIndexOf(_ elem: Element, isOrderedBefore: (Element, Element) -> Bool) -> Int {
        var lo = 0
        var hi = self.count - 1
        while lo <= hi {
            let mid = (lo + hi)/2
            if isOrderedBefore(self[mid], elem) {
                lo = mid + 1
            } else if isOrderedBefore(elem, self[mid]) {
                hi = mid - 1
            } else {
                return mid // found at position mid
            }
        }
        return lo // not found, would be inserted at position lo
    }
}

与 indexOfObject:inSortedRange:options:usingComparator: 一样，假定数组根据比较器排序。如果元素已经存在于数组，或者在保留顺序的情况下可以插入的索引。这个对应NSArray方法的NSBinarySearchingInsertionIndex

用法:

let newElement = "c"
let index = myArray.insertionIndexOf(newElement) { $0 < $1 } // Or: myArray.indexOf(c, <)
myArray.insert(newElement, at: index)