Вот возможная реализация в 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:
, предполагается, что массив сортируется относительно компаратора. Он возвращает либо (любой) индекс элемента, если элемент уже присутствует в массиве, либо индекс, в который он может быть вставлен при сохранении порядка. Это соответствует NSBinarySearchingInsertionIndex
метода NSArray
.
Использование:
let newElement = "c"
let index = myArray.insertionIndexOf(newElement) { $0 < $1 } // Or: myArray.indexOf(c, <)
myArray.insert(newElement, atIndex: index)
В swift 3 вы можете использовать index(where:)
:
var myArray = ["a", "b", "d", "e"]
let newElement = "c"
if let index = myArray.index(where: { $0 > newElement }) {
myArray.insert(newElement, at: index)
}
Обратите внимание, что в этом случае вам нужно отменить условие внутри закрытия (т. е. >
вместо <
для увеличения элементов в массиве), потому что интересующий вас индекс - это первый элемент, который НЕ соответствует предикату. Кроме того, этот метод вернет nil
, если вновь вставленный элемент будет последним в массиве (newElement = "z"
в примере выше.
Для удобства это можно обернуть в отдельную функцию который будет обрабатывать все эти проблемы:
extension Collection {
func insertionIndex(of element: Self.Iterator.Element,
using areInIncreasingOrder: (Self.Iterator.Element, Self.Iterator.Element) -> Bool) -> Index {
return index(where: { !areInIncreasingOrder($0, element) }) ?? endIndex
}
}
Использование:
var myArray = ["a", "b", "d", "e"]
let newElement = "c"
let index = myArray.insertionIndex(of: newElement, using: <)
myArray.insert(newElement, at: index)
Если вы знаете, что ваш массив отсортирован, вы можете использовать этот метод - он будет работать с массивами любого типа. Он будет перемещаться по всему массиву каждый раз, поэтому не используйте его с большими массивами - перейдите к другому типу данных, если у вас есть большие потребности!
func insertSorted<T: Comparable>(inout seq: [T], newItem item: T) {
let index = seq.reduce(0) { $1 < item ? $0 + 1 : $0 }
seq.insert(item, atIndex: index)
}
var arr = [2, 4, 6, 8]
insertSorted(&arr, newItem: 5)
insertSorted(&arr, newItem: 3)
insertSorted(&arr, newItem: -3)
insertSorted(&arr, newItem: 11)
// [-3, 2, 3, 4, 5, 6, 8, 11]
Двоичное дерево поиска здесь - путь.
В упорядоченном массиве возьмите элемент посередине и посмотрите, больше ли объект в этой позиции, чем ваш новый объект. Таким образом, вы можете забыть половину элементов массива с помощью одного сравнения.
Повторите этот шаг с оставшейся половиной. Опять же, при одном сравнении вы можете забыть половину оставшихся объектов. Ваш счетчик целевых элементов теперь составляет четверть от размера массива в начале с двумя сравнениями.
Повторяйте это, пока не найдете правильную позицию для вставки нового элемента.