Sublinear solution for identifying inserted elements

FindInsertions.swift

func findInsertions<C: Collection>(old: C, new: C) -> [C.Index]
where C.Element: Equatable, C.Indices.Index == Int
{
    var result: [C.Index] = .init()
    var offsetInOld = 0
    while offsetInOld < old.count {
        let nextInsertInNew = firstOffset(in: offsetInOld..<old.count) { off in
            return new[offset: off + result.count] != old[offset: off]
        } + result.count
        if nextInsertInNew >= new.count {
            break
        }

        offsetInOld = nextInsertInNew - result.count
        let subsequentMatchInNew: Int
        if offsetInOld < old.count && (nextInsertInNew + 1) < new.count {
            subsequentMatchInNew = firstOffset(in: (nextInsertInNew + 1)..<new.count) { off in
                new[offset: off] == old[offset: offsetInOld]
            }
        } else {
            subsequentMatchInNew = new.count
        }

        let newInsertedIndexes = new.index(offset: nextInsertInNew)..<new.index(offset: subsequentMatchInNew)
        for index in newInsertedIndexes {
        }
        result.append(contentsOf: newInsertedIndexes)
        offsetInOld = subsequentMatchInNew - result.count
    }
    return result
}

// MARK: Scaffolding and Jigs

// 2log(n) search
private func firstOffset(in range: Range<Int>, where cond: (Int) -> Bool) -> Int {
    guard !range.isEmpty else {
        return range.upperBound
    }
    if cond(range.lowerBound) {
        return range.lowerBound
    }

    var stride = 1
    var index = range.lowerBound + stride
    while index < range.upperBound && !cond(index) {
        stride *= 2
        index += stride
    }

    while stride > 1 {
        stride /= 2
        if index >= range.upperBound || !cond(index) {
            index -= stride
        } else {
            index += stride
        }
    }
    return index
}

private extension Collection {
    func index(offset: Int) -> Index {
        return index(startIndex, offsetBy: offset)
    }

    subscript(offset offset: Int) -> Element {
        return self[index(offset: offset)]
    }
}

The add inserts until next match needs to be:

        // add inserts until next match
        while new[offset: offset + result.count] != old[offset: offset] {
            result.append(new.index(offset: offset + result.count))
        }
        offset += 1

After all this time I ought to have known better than to mix index domains between collections, yet here we are