Kāda ir elementa meklēšanas sarežģītība masīvā Swift?

Swift-ā tipisks nepareizi sakārtots masīvs (piemēram, Array<Element>) elementa meklēšanas sarežģītība ir O(n), kur n ir masīva elementu skaits. Tas ir tāpēc, ka sliktākajā gadījumā var būt nepieciešams pārbaudīt visus masīva elementus, lai atrastu meklēto.

Tomēr, ja masīvs ir sakārtots, var izmantot bināro meklēšanu, kas ir O(log n). Swift nodrošina binarySearch metodi sakārtotām kolekcijām.

Lineārās meklēšanas piemērs:

let array = [1, 5, 2, 8, 3]
let elementToFind = 8

for element in array {
    if element == elementToFind {
        // Elements atrasts
        break
    }
}

Sakārtotā masīvā binārās meklēšanas piemērs:

let sortedArray = [1, 2, 3, 5, 8]
let elementToFind = 5

if let index = sortedArray.firstIndex(where: { $0 == elementToFind }) {
    // Elements atrasts indeksā
}