Méthodes de recherche : séquentielle et dichotomique

Plan de cours

Trouver vite, c'est diviser

Chercher un élément dans un tableau est une opération omniprésente : un mot dans un dictionnaire, un produit dans un catalogue, un élève dans une liste. Selon la structure des données, deux méthodes s'opposent radicalement par leur efficacité.

Objectifs d'apprentissage

• Comparer séquentielle et dichotomique
• Implémenter les deux algorithmes
• Coût en fonction de n
• Choisir selon le contexte

Concepts clés

1. Recherche séquentielle — parcours linéaire, O(n).
2. Recherche dichotomique — par division, O(log n), exige un tableau trié.
3. Comparaison de coût — 1 M éléments → 1 M vs 20 comparaisons.
4. Trade-off du tri — vaut-il la peine de trier avant ?

Avant de commencer — qu'est-ce que vous savez déjà ?

• Q1. Comment cherchez-vous un mot dans un dictionnaire papier ? Pas du tout au hasard, j'imagine. Pourquoi ?
• Q2. Pour chercher 17 dans [3, 7, 12, 17, 22, 29, 35], pouvez-vous utiliser une stratégie « plus efficace » que parcourir un par un ?
• Q3. Quel est le pire cas pour la recherche séquentielle ?

1. Le contenu du cours

1.1 Recherche séquentielle

Fonction recherche_sequentielle(t : tableau de entier ; cible : entier) → entier
    Pour i De 0 À long(t) - 1 Faire
        Si t[i] = cible Alors
            Retourner(i)
        FinSi
    FinPour
    Retourner(-1)
FinFonction

def recherche_sequentielle(t: list[int], cible: int) -> int:
    for i in range(len(t)):
        if t[i] == cible:
            return i
    return -1

Coût

• Meilleur cas : élément en position 0 → 1 comparaison.
• Pire cas : élément absent ou en dernière position → n comparaisons.
• Moyenne : n / 2 comparaisons.

On parle de complexité linéaire O(n) : le coût croît proportionnellement à la taille du tableau.

Avantage

• Aucune contrainte sur le tableau (non trié, valeurs en doublon, types variés).
• Simple à coder, peu d'erreurs possibles.

1.2 Recherche dichotomique (ou binaire)

Fonction recherche_dichotomique(t : tableau trié ; cible : entier) → entier
    gauche ← 0
    droite ← long(t) - 1
    Tant que gauche ≤ droite Faire
        milieu ← (gauche + droite) div 2
        Si t[milieu] = cible Alors
            Retourner(milieu)
        Sinon
            Si t[milieu] < cible Alors
                gauche ← milieu + 1
            Sinon
                droite ← milieu - 1
            FinSi
        FinSi
    FinTantQue
    Retourner(-1)
FinFonction

def recherche_dichotomique(t: list[int], cible: int) -> int:
    gauche = 0
    droite = len(t) - 1
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if t[milieu] == cible:
            return milieu
        elif t[milieu] < cible:
            gauche = milieu + 1
        else:
            droite = milieu - 1
    return -1

Visualisation — cas générique

Chercher 22 dans [3, 7, 12, 17, 22, 29, 35] (indices 0 à 6) :

3 étapes pour un tableau de 7 éléments — à comparer aux 5 étapes qu'aurait demandé une recherche séquentielle (parcours 3 → 7 → 12 → 17 → 22). Le gain est déjà visible sur un petit exemple ; il devient écrasant pour 1 000 ou 1 000 000 d'éléments.

Cas chanceux — la cible est pile au milieu

Chercher 17 dans le même tableau :

1 seule comparaison suffit ! C'est le meilleur cas de la dichotomie. Au pire cas, on fait log₂(n) étapes — pour 1 000 000 d'éléments, au plus 20 comparaisons.

Cas absent : chercher 13

Coût

• À chaque étape, l'intervalle est divisé par 2.
• Pour n éléments, le nombre d'étapes est environ log₂(n).
• Complexité logarithmique O(log n).

1.3 Comparaison chiffrée

Sur 1 million d'éléments, la dichotomie est 50 000 fois plus rapide.

1.4 Trace : dichotomique pas-à-pas

Chercher 42 dans [3, 8, 15, 22, 30, 42, 51, 65, 78] :

2. Exercices pratiques

Niveau Débutant — Type bac courant

def premier_negatif(t: list[int]) -> int:
    for i in range(len(t)):
        if t[i] < 0:
            return i
    return -1

print(premier_negatif([3, 7, -2, 5, -8]))   # 2
print(premier_negatif([1, 2, 3]))            # -1

Niveau Intermédiaire — Type bac difficile

def toutes_les_occurrences(t: list[int], cible: int) -> list[int]:
    indices = []
    for i in range(len(t)):
        if t[i] == cible:
            indices.append(i)
    return indices

print(toutes_les_occurrences([1, 3, 5, 3, 7, 3], 3))   # [1, 3, 5]

Niveau Avancé — Hors bac (bonus)

def dicho_iter(t: list[int], cible: int) -> int:
    g, d = 0, len(t) - 1
    while g <= d:
        m = (g + d) // 2
        if t[m] == cible:
            return m
        elif t[m] < cible:
            g = m + 1
        else:
            d = m - 1
    return -1

def dicho_rec(t: list[int], cible: int, g: int = 0, d: int = -1) -> int:
    if d == -1:
        d = len(t) - 1
    if g > d:
        return -1
    m = (g + d) // 2
    if t[m] == cible:
        return m
    elif t[m] < cible:
        return dicho_rec(t, cible, m + 1, d)
    else:
        return dicho_rec(t, cible, g, m - 1)

print(dicho_rec([3, 8, 15, 22, 30, 42, 51, 65, 78], 42))   # 5

⚠️ Erreurs fréquentes au bac

Avant le quiz, mémorisez ces pièges classiques qui font perdre des points :

• Erreur 1. Appliquer la dichotomie sur un tableau non trié → résultats faux (pas une erreur d'exécution, juste un mauvais résultat).
• Erreur 2. Initialiser gauche = 1 au lieu de 0 en Python. Décalage classique d'un cran.
• Erreur 3. Boucle Tant que gauche < droite au lieu de gauche ≤ droite. Rate le cas où l'élément est à l'indice où g et d se rejoignent.
• Erreur 4. Oublier de retourner -1 (ou une valeur signalant l'absence) quand l'élément n'est pas trouvé.

3. Quiz de vérification

En résumé

• ✅ Séquentielle : O(n), pas de pré-requis.
• ✅ Dichotomique : O(log n), tableau trié obligatoire.
• ✅ Sur 1 M d'éléments : séquentielle = 1 M comparaisons vs dichotomique = 20.
• ✅ Tri préalable rentable si on fait beaucoup de recherches.

Prochaine leçon : Méthodes de tri — sélection, bulles, insertion. Comment trier pour pouvoir ensuite chercher en dichotomie.