Recherche séquentielle

La recherche séquentielle constitue l'approche fondamentale pour localiser un élément dans une collection. Son principe repose sur l'examen successif de chaque élément jusqu'à identifier la cible ou épuiser tous les éléments.

Méthodes d'implémentation

func rechercheLineaire<T: Equatable>(_ collection: [T], _ cible: T) -> Int? {
    for (position, valeur) in collection.enumerated() {
        if valeur == cible {
            return position
        }
    }
    return nil
}

Alternative utilisent les fonctions d'ordre supérieur :

func rechercheLineaire<T: Equatable>(_ collection: [T], _ cible: T) -> Int? {
    return collection.firstIndex { $0 == cible }
}

Analyse de performance

Domaines d'application

• Collections de petite taille
• Données non triées
• Recherches ponctuelles

Recherche dichotomique

La recherche dichotomique exploite la nature triée des données pour diviser systématiquement l'espace de recherche.

Version itérative

func rechercheDichotomique<T: Comparable>(_ collection: [T], _ cible: T) -> Int? {
    var debut = 0
    var fin = collection.count
    
    while debut < fin {
        let milieu = debut + (fin - debut) / 2
        
        if collection[milieu] == cible {
            return milieu
        } else if collection[milieu] < cible {
            debut = milieu + 1
        } else {
            fin = milieu
        }
    }
    return nil
}

Version récursive

func rechercheDichotomique<T: Comparable>(_ collection: [T], _ cible: T, _ intervalle: Range<Int>) -> Int? {
    guard intervalle.lowerBound < intervalle.upperBound else {
        return nil
    }
    
    let milieu = intervalle.lowerBound + (intervalle.upperBound - intervalle.lowerBound) / 2
    
    if collection[milieu] > cible {
        return rechercheDichotomique(collection, cible, intervalle.lowerBound..<milieu cible="" collection="" else="" if="" milieu="" recherchedichotomique="" return=""></milieu>

Comparaison des approches

Optimisations avancées

Recherche par interpolation pour données uniformément distribuées :

func rechercheInterpolation(_ collection: [Int], _ cible: Int) -> Int? {
    var debut = 0
    var fin = collection.count - 1
    
    while debut <= fin && cible >= collection[debut] && cible <= collection[fin] {
        if debut == fin {
            return collection[debut] == cible ? debut : nil
        }
        
        let position = debut + ((cible - collection[debut]) * (fin - debut)) / (collection[fin] - collection[debut])
        
        if collection[position] == cible {
            return position
        } else if collection[position] < cible {
            debut = position + 1
        } else {
            fin = position - 1
        }
    }
    return nil
}

Analyse comparative

Les tests de performance révèlent des différences significatives selon la taille des données :

• Petites collections : la recherche séquentielle s'avère souvent plus efifcace
• Grandes colelctions triées : la recherche dichotomique présente un avantage décisif
• Collections dynamiques : le coût de tri peut contrebalancer les bénéfices de la dichotomie

Stratégie hybride

func rechercheOptimisee<T: Comparable>(_ collection: [T], _ cible: T) -> Int? {
    if collection.count < 50 {
        return collection.firstIndex { $0 == cible }
    } else {
        let collectionTriee = collection.sorted()
        return rechercheDichotomique(collectionTriee, cible)
    }
}