Aká je zložitosť vyhľadávania prvku v poli v Swift?

Zložitosť vyhľadávania prvku v typickom neusporiadanom poli (napríklad Array<Element>) v Swift je O(n), kde n je počet prvkov v poli. To je spôsobené tým, že v najhoršom prípade môže byť potrebné prejsť všetky prvky poľa, aby sa našiel požadovaný prvok.

Avšak, ak je pole zoradené, je možné použiť binárne vyhľadávanie, ktoré má zložitosť O(log n). Swift poskytuje metódu binarySearch pre zoradené kolekcie.

Príklad lineárneho vyhľadávania:

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

for element in array {
    if element == elementToFind {
        // Prvok nájdený
        break
    }
}

Príklad binárneho vyhľadávania v zoradenom poli:

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

if let index = sortedArray.firstIndex(where: { $0 == elementToFind }) {
    // Prvok nájdený na indexe
}