Kokia yra elemento paieškos sudėtingumas masyve Swift?

Swift kalboje tipinis nesutvarkytas masyvas (pavyzdžiui, Array<Element>) elementų paieškos sudėtingumas yra O(n), kur n yra masyvo elementų skaičius. Tai yra todėl, kad blogiausiu atveju gali prireikti peržiūrėti visus masyvo elementus, kad rastumėte ieškomą.

Tačiau, jei masyvas yra surūšiuotas, galima naudoti dvejetainę paiešką, kuri turi sudėtingumą O(log n). Swift teikia binarySearch metodą surūšiuotoms kolekcijoms.

Pavyzdys linijinės paieškos:

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

for element in array {
    if element == elementToFind {
        // Elementas rastas
        break
    }
}

Pavyzdys dvejetainės paieškos surūšiuotame masyve:

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

if let index = sortedArray.firstIndex(where: { $0 == elementToFind }) {
    // Elementas rastas indeksu
}