Jaka jest złożoność wyszukiwania elementu w tablicy w Swift?

Złożoność wyszukiwania elementu w typowej nieuporządkowanej tablicy (np. Array<Element>) w Swift wynosi O(n), gdzie n to liczba elementów w tablicy. Wynika to z faktu, że w najgorszym przypadku konieczne może być przeszukanie wszystkich elementów tablicy.

Jednak jeśli tablica jest posortowana, można użyć wyszukiwania binarnego, które ma złożoność O(log n). Swift udostępnia metodę binarySearch dla posortowanych kolekcji.

Przykład wyszukiwania liniowego:

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

for element in array {
    if element == elementToFind {
        // Element znaleziony
        break
    }
}

Przykład wyszukiwania binarnego w posortowanej tablicy:

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

if let index = sortedArray.firstIndex(where: { $0 == elementToFind }) {
    // Element znaleziony na indeksie
}