Say you have a large 'before' array, and an 'after' array where the elements have identity but aren't otherwise sorted or anything and need to determine where insertions happened (presumably a much smaller number of them, no reorders, no deletions). Is there a name for this collection operation? Is there a better way than this binary-search-inspired O(log(N) * M) N=original, M=insertions approach?
![func findInsertions<T: Equatable>(old: ArraySlice<T>, new: ArraySlice<T>) -> [Int] {
print("old: \(old) new: \(new)")
let last = old.count-1
let lastOld = old.startIndex + last
let lastNew = new.startIndex + last
guard old[lastOld] != new[lastNew] else { return [] }
if last == 0 { return [new.startIndex] }
let middle = old.count/2
let oldMidIndex = old.startIndex + middle
let newMidIndex = new.startIndex + middle
let firstHalf = findInsertions(old: old[..<oldMidIndex], new: new)
let secondHalf = findInsertions(old: old[oldMidIndex...], new: new[(newMidIndex + firstHalf.count)...])
return firstHalf + secondHalf
}
func findInsertions<T: Equatable>(old: [T], new: [T]) -> [Int] {
let result = findInsertions(old: old[...], new: new[...])
let leftoverIndex = result.count + old.count
let leftover = new[leftoverIndex...].enumerated().map { leftoverIndex + $0.offset }
return result + leftover
}](https://social-coop-media.ams3.cdn.digitaloceanspaces.com/media_attachments/files/114/830/861/019/316/118/original/120955eac96bd146.png)