Recherche par dichotomie

Vue d'ensemble

Chercher une valeur dans un tableau trié ne demande pas de tout parcourir : la recherche par dichotomie coupe l'espace de recherche en deux à chaque étape et trouve (ou élimine) la valeur en un temps logarithmique. C'est l'un des tout premiers réflexes attendus aux concours, et la brique de base d'innombrables algorithmes. Cette fiche te fait écrire le code, le décrypter ligne par ligne, le suivre pas à pas, puis en prouver la terminaison et la correction.

Au programme (tronc commun, 1^re année — BO 2021) — Recherche séquentielle et recherche par dichotomie dans un tableau trié ; coût logarithmique ; lien avec la récursivité ; notion d'invariant de boucle.

Prérequis

Manipuler les listes Python : indexation t[i], longueur len(t)
Boucle while et division entière //
Notion de tableau trié par ordre croissant

🎯 Accompagnement Majorant

Le code « marche » mais tu ne vois pas ce qu'il se passe à l'intérieur ? C'est exactement là que se jouent les points en informatique. Nos mentors alumni X · Centrale · Mines reprennent chaque ligne avec toi, sur tes propres DS, jusqu'à ce que tu déroules un algorithme les yeux fermés.

Trouver un mentor →

1. Le principe de la dichotomie

Définition 1.1 — Recherche dichotomique

On cherche une valeur x dans un tableau t trié par ordre croissant. On maintient un intervalle d'indices [g, d] susceptible de contenir x. À chaque étape, on compare x à l'élément du milieu m et on élimine la moitié qui ne peut pas contenir x.

def recherche(t, x):
    # t est trié par ordre croissant
    g, d = 0, len(t) - 1
    while g <= d:
        m = (g + d) // 2
        if t[m] == x:
            return m
        elif t[m] < x:
            g = m + 1
        else:
            d = m - 1
    return -1  # x est absent

🔍 Décryptage ligne par ligne

g, d = 0, len(t) - 1On délimite la zone de recherche. g (gauche) pointe le premier indice, d (droite) le dernier. L'intervalle [g, d] est « l'endroit où x peut encore se cacher » — au départ, tout le tableau.

while g <= d:On répète tant qu'il reste des candidats. Dès que g dépasse d, l'intervalle est vide : c'est que x n'y était pas.

m = (g + d) // 2On vise le milieu. // est la division entière ; m est l'indice central de l'intervalle, l'élément qu'on va comparer à x.

if t[m] == x:
    return m

Trouvé. Si l'élément du milieu vaut x, on renvoie sa position m et on arrête tout.

elif t[m] < x:
    g = m + 1

Trop petit → on part à droite. Le tableau étant trié, si le milieu est plus petit que x, alors x est forcément après m. On jette toute la moitié gauche en amenant g à m + 1 (on exclut m, déjà testé).

else:
    d = m - 1

Trop grand → on part à gauche. Sinon le milieu dépasse x : on jette la moitié droite en ramenant d à m - 1.

return -1Absent. Si la boucle se vide sans rien trouver, x n'est pas dans t : on renvoie -1 (code habituel pour « pas trouvé »).

Exécution pas à pas — recherche([1, 3, 5, 7, 9], 7)
Tour	g	d	m	t[m]	Comparaison	Action
1	0	4	2	5	5 < 7	g ← 3
2	3	4	3	7	7 = 7	renvoie 3 ✓

💡 L'astuce (et pourquoi c'est rapide). À chaque tour, la moitié des éléments restants est éliminée d'un coup. Pour un tableau de 1000 éléments, environ 10 comparaisons suffisent (car

2^{10} = 1024 &gt; 1000

) au lieu de 1000 pour une recherche naïve : c'est tout l'intérêt du coût en

O (lo g n)

2. Terminaison et correction

📐 Méthode — prouver un algorithme de recherche.

Terminaison : on exhibe un variant, une quantité entière positive qui décroît strictement à chaque tour. Ici d - g diminue d'au moins 1 à chaque passage (on remplace g par m + 1 ou d par m - 1), donc la boucle s'arrête.
Invariant : on énonce une propriété vraie avant la boucle et préservée à chaque tour. Ici : si x est dans t, alors x est dans t[g..d].
Correction : à la sortie, soit on a renvoyé m avec t[m] = x, soit l'intervalle est vide (g > d) et l'invariant garantit alors que x est absent.

Théorème 2.1 — Correction de la recherche dichotomique ★ À savoir justifier

Pour tout tableau t trié par ordre croissant et toute valeur x, recherche(t, x) renvoie un indice m tel que t[m] = x si x figure dans t, et -1 sinon.

Démonstration

Terminaison. Posons $v = d - g$ . Initialement $v = n - 1$ . À chaque tour où l'on ne renvoie pas, on effectue soit g = m + 1, soit d = m - 1 avec $g \leq m \leq d$ ; dans les deux cas $v$ diminue strictement d'au moins 1. Comme la boucle s'exécute tant que $g \leq d$ c'est-à-dire $v \geq 0$ , le variant $v$ est un entier positif strictement décroissant : la boucle termine.

Invariant. Notons $P$ : « si x apparaît dans t, alors il apparaît dans t[g..d] ». $P$ est vrai avant la boucle (l'intervalle est tout le tableau). Supposons $P$ vrai en début de tour. Comme t est trié : si t[m] < x, aucune case d'indice $\leq m$ ne peut valoir x, donc si x est présent il est dans t[m+1..d] : $P$ reste vrai après g = m + 1. Le cas t[m] > x est symétrique. $P$ est donc un invariant.

Correction. À la sortie, deux cas. Ou bien on a renvoyé m avec t[m] = x : le résultat est correct. Ou bien g > d : l'intervalle t[g..d] est vide, et par $P$ , x n'apparaît pas dans t ; renvoyer -1 est correct. $■$

3. Version récursive

La même idée s'écrit naturellement de façon récursive : chercher dans t[g..d], c'est chercher dans une moitié de t[g..d]. Les bornes g et d deviennent des paramètres.

def recherche_rec(t, x, g, d):
    if g > d:
        return -1              # intervalle vide : absent
    m = (g + d) // 2
    if t[m] == x:
        return m
    elif t[m] < x:
        return recherche_rec(t, x, m + 1, d)   # moitié droite
    else:
        return recherche_rec(t, x, g, m - 1)   # moitié gauche

# appel initial : recherche_rec(t, x, 0, len(t) - 1)

📝 Récursivité et terminaison. Le cas de base est g > d (intervalle vide). À chaque appel, la taille d - g diminue strictement : la profondeur de récursion est en

O (lo g n)

, comme le nombre de tours de la version itérative.

4. Erreurs classiques en copie

⚠ Oublier que le tableau doit être trié. La dichotomie n'a aucun sens sur un tableau non trié : la comparaison au milieu ne dit plus dans quelle moitié chercher. Toujours vérifier (ou signaler) cette précondition.

⚠ Écrire while g < d au lieu de while g <= d. Avec <, l'intervalle réduit à un seul élément (g = d) n'est jamais testé : on peut renvoyer -1 alors que la valeur y était.

⚠ Réaffecter g = m (ou d = m) au lieu de m ± 1. Si l'intervalle ne se réduit plus (cas de deux éléments), la boucle tourne indéfiniment. On exclut toujours m, déjà comparé.

⚠ Calculer le milieu hors de la boucle. m doit être recalculé à chaque tour à partir des bornes courantes g et d, sinon on compare toujours le même élément.

5. Exercices d'application

Fais-les sur papier avant d'ouvrir le corrigé, puis passe au quiz en bas de fiche.

Exo 1Dichotomie et doublonsIntermédiaire

Que renvoie recherche([1, 4, 4, 4, 9], 4) ? La fonction renvoie-t-elle forcément l'indice de la première occurrence ?

Voir la correction détaillée

g=0, d=4 → m = (0+4)//2 = 2 ; t[2] = 4.

t[m] == x (4 = 4) → on renvoie immédiatement 2.

Non, ce n'est pas la première occurrence (qui est à l'indice 1) : dès qu'un 4 est trouvé au milieu, la fonction s'arrête. La dichotomie renvoie un indice d'une valeur égale à x, pas nécessairement le plus petit. Pour la première occurrence, il faut une variante.

Exo 2Compter les toursDifficile

Dans le pire cas, combien de tours de boucle au maximum pour un tableau de n = 100 éléments ? Justifie.

Voir la correction détaillée

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

Le pire cas fait

⌊ lo g_{2} n ⌋ + 1

tours.

Pour

n = 100

2^6 = 64 &lt; 100 \leq 128 = 2^7

, donc

⌊ lo g_{2} 100 ⌋ = 6

et il faut au plus 7 tours. C'est bien un coût en

O (lo g n)

Exo 3Adapter le codeIntermédiaire

Écris une fonction appartient(t, x) qui renvoie True si x est dans le tableau trié t, False sinon, en réutilisant la dichotomie.

Voir la correction détaillée

Il suffit de renvoyer True quand on trouve, et False en fin de boucle :

def appartient(t, x):
    g, d = 0, len(t) - 1
    while g <= d:
        m = (g + d) // 2
        if t[m] == x:
            return True
        elif t[m] < x:
            g = m + 1
        else:
            d = m - 1
    return False

On peut aussi l'écrire en une ligne à partir de la première fonction : return recherche(t, x) != -1.

6. Pour aller plus loin

La dichotomie se réinvestit tout au long du programme :

Récursivité — la version récursive est un exemple canonique de « diviser pour régner ».
Complexité — le raisonnement « on divise par 2 » donne directement le coût $O (lo g n)$ .
Dichotomie sur une réponse — chercher par dichotomie la plus petite valeur vérifiant une condition monotone (méthode très fréquente en exercice).

Récap final — Ce qu'il faut absolument retenir

À la veille d'une khôlle ou d'un DS, parcours cette checklist : tu dois pouvoir répondre « oui, sans hésiter » à chaque question.

Sais-tu écrire la recherche dichotomique itérative de mémoire (bornes g, d, milieu m) ?
Sais-tu expliquer pourquoi le tableau doit être trié ?
Sais-tu dérouler l'algorithme sur un exemple et remplir une table de trace ?
Sais-tu pourquoi la condition est g <= d et non g < d ?
Sais-tu énoncer le variant (d - g) et l'invariant de la boucle ?
Sais-tu justifier la complexité en $O (lo g n)$ ?
Sais-tu écrire la version récursive et identifier son cas de base ?

À savoir refaire

Correction de la dichotomie — variant d - g, invariant « si x ∈ t alors x ∈ t[g..d] ».

Vue d'ensemble

Prérequis

1. Le principe de la dichotomie

2. Terminaison et correction

3. Version récursive

4. Erreurs classiques en copie

5. Exercices d'application

6. Pour aller plus loin

Récap final — Ce qu'il faut absolument retenir

À savoir refaire

Quiz — Dichotomie

Fiches associées

Variables, types et affectations

Conditions et booléens

Boucles for et while

Fonctions : paramètres et valeurs de retour

Listes et chaînes de caractères

Lire, tester et corriger un programme

Tu veux aller plus loin sur ce chapitre ?