Quelle est la complexité de rechercher un élément dans un tableau en Swift?

La complexité de rechercher un élément dans un tableau non trié typique (par exemple, Array<Element>) en Swift est de O(n), où n est le nombre d'éléments dans le tableau. Cela est dû au fait que, dans le pire des cas, il peut être nécessaire de parcourir tous les éléments du tableau pour trouver l'élément.

Cependant, si le tableau est trié, on peut utiliser la recherche binaire, qui a une complexité de O(log n). Swift fournit la méthode binarySearch pour les collections triées.

Exemple de recherche linéaire :

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

for element in array {
    if element == elementToFind {
        // Élément trouvé
        break
    }
}

Exemple de recherche binaire dans un tableau trié :

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

if let index = sortedArray.firstIndex(where: { $0 == elementToFind }) {
    // Élément trouvé à l'indice
}