Quelles méthodes peuvent être utilisées pour rechercher rapidement un élément dans un tableau trié, en minimisant le temps?

Pour rechercher rapidement un élément dans un tableau trié, on utilise généralement l'algorithme de recherche binaire. Il minimise le temps de recherche, car il fonctionne en temps O(log n), où n est la taille du tableau.

Idée de la recherche binaire :

• Comparer l'élément recherché avec l'élément au milieu du tableau.
• Si ils sont égaux, l'élément est trouvé.
• Si l'élément recherché est inférieur, rechercher dans la moitié gauche.
• Si il est supérieur, dans la moitié droite.

Sur iOS (Swift), vous pouvez utiliser la méthode binarySearch ou l'implémenter vous-même.

Exemple en Swift :

func binarySearch<T: Comparable>(_ array: [T], target: T) -> Int? {
    var low = 0
    var high = array.count - 1
    while low <= high {
        let mid = (low + high) / 2
        if array[mid] == target {
            return mid
        } else if array[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return nil
}

let sortedArray = [1, 3, 5, 7, 9]
if let index = binarySearch(sortedArray, target: 5) {
    print("Élément trouvé à la position \(index)")
} else {
    print("Élément non trouvé")
}