Recherche dichotomique - Recherche NSI

Principe

diviser pour régner

On compare la cible au milieu du segment. Selon le résultat, on élimine la moitié gauche ou droite et on recommence.

Précondition obligatoire

Le tableau doit être trié (ordre croissant ou décroissant)

Invariant

Si la cible existe, elle est toujours dans l'intervalle [gauche, droite]

Réduction

Chaque étape divise la zone de recherche par 2

Synonyme

Recherche dichotomique = recherche par dichotomie = binary search

À retenir

Les deux codes complets sont dans la section Les deux exemples Python ci-dessous.

Complexité T(n) et O(log n)

logarithmique

À chaque tour, la taille de l'intervalle est divisée par 2.

Nombre d'étapes

Au plus log₂(n) + 1 comparaisons (pire cas)

Exemple

n = 1 024 → au pire ≈ 10 comparaisons ; n = 1 000 000 → ≈ 20

Pire cas

T(n) = O(log n)

Meilleur cas

Cible au milieu du premier test → O(1)

À retenir

Beaucoup plus rapide que O(n) pour les grands tableaux triés.

Avantages

efficacité

Choix privilégié dès que le tri est disponible et n grand.

Très rapide

O(log n) : croissance quasi négligeable

Idéal pour recherches répétées

Sur un grand tableau déjà trié

Base de nombreux algorithmes

Même idée en « diviser pour régner »

Inconvénients

contraintes

Pas utilisable dans tous les contextes.

Tri obligatoire

Coût du tri O(n log n) si le tableau ne l'est pas déjà

Tableau statique

Accès par indice au milieu ; mal adapté aux listes chaînées simples

Plus complexe à coder

Indices gauche/droite, risque de boucle infinie si mal écrit

Petit n

Le surcoût du tri peut ne pas compenser sur très petites listes

📋 Visualisation (tableau trié de 9 éléments)

Recherche de 7 dans [1, 3, 5, 7, 9, 11, 13, 15, 17]

Étape 1 : milieu index 4 → tab[4]=9  > 7  → garder gauche [0..3]
Étape 2 : milieu index 1 → tab[1]=3  < 7  → garder droite [2..3]
Étape 3 : milieu index 2 → tab[2]=5  < 7  → garder [3..3]
Étape 4 : index 3 → tab[3]=7  trouvé

Erreur fréquente en contrôle

Appliquer la dichotomie sur un tableau non trié donne un résultat faux même si l'algorithme « tourne ».

💻 Les deux exemples Python

Même objectif : retourner l'indice de la cible, ou -1 si absente. Compare les deux implémentations côte à côte.

1. Recherche séquentielle (O(n))

Fonctionne sur un tableau non trié. On avance indice par indice.

recherche_sequentielle.py

def recherche_sequentielle(tab, cible):
    for i in range(len(tab)):
        if tab[i] == cible:
            return i
    return -1

# Tableau non trié possible
notes = [12, 15, 9, 18, 11]
print(recherche_sequentielle(notes, 18))  # 3
print(recherche_sequentielle(notes, 7))   # -1

2. Recherche dichotomique (O(log n))

Nécessite un tableau trié. On coupe l'intervalle en deux à chaque étape.

recherche_dichotomique.py

def dichotomie(tab, cible):
    g, d = 0, len(tab) - 1
    while g <= d:
        m = (g + d) // 2
        if tab[m] == cible:
            return m
        elif tab[m] < cible:
            g = m + 1
        else:
            d = m - 1
    return -1

# Tableau trié obligatoire
ages = [2, 5, 8, 12, 16, 21]
print(dichotomie(ages, 8))   # 2
print(dichotomie(ages, 10))  # -1

Recherche dichotomique (dichotomie)