Numérique et sciences informatiques (spécialité) · Première

La recherche dichotomique : cours de NSI en Première

Publié le 6 novembre 2026 · Mis à jour le 6 novembre 2026 · Signaler une erreur

L'essentiel

La recherche dichotomique trouve la position d'une valeur dans un tableau trié en comparant la valeur cherchée à l'élément du milieu, puis en gardant une seule moitié.³
À chaque tour de boucle, la zone de recherche est divisée par 2 : on dit qu'on procède par dichotomie.²
Le nombre de comparaisons est logarithmique en la taille du tableau, alors que la recherche séquentielle est linéaire.³
La boucle while n'est pas bornée à l'avance : on prouve qu'elle s'arrête avec un variant et qu'elle est correcte avec un invariant.²
Le tableau doit être trié : sur un tableau non trié, le résultat n'a aucune valeur.

Pourquoi chercher mieux qu'élément par élément ?

Tu cherches un mot dans un dictionnaire papier. Tu ne lis pas toutes les pages depuis la première : tu ouvres vers le milieu, tu regardes où tu es tombé, puis tu sais s'il faut aller vers le début ou vers la fin. Tu recommences sur la partie restante. En quelques essais, tu y es.

En programmation, c'est exactement l'idée de la recherche dichotomique. Elle sert à trouver la position d'un élément dans un tableau trié.³ Dans ce cours, tu vas écrire l'algorithme en Python, comprendre pourquoi il s'arrête toujours, pourquoi il renvoie un résultat correct, et mesurer son coût.

Tu connais déjà le parcours séquentiel d'un tableau : on examine les cases une par une. C'est la méthode la plus simple, elle fonctionne même si le tableau n'est pas trié, mais son temps de calcul est linéaire : si le tableau double de taille, le travail double.³ Tu connais aussi les tris par insertion et par sélection : ils servent justement à obtenir un tableau trié, condition indispensable pour la recherche dichotomique.

La recherche dichotomique appartient à la famille des algorithmes de recherche, et elle traite efficacement des données représentées dans un tableau ordonné.²

Le principe de la dichotomie

Pourquoi le tri est-il indispensable ? Quand tu regardes la case du milieu et que sa valeur est plus petite que celle que tu cherches, tu peux éliminer toute la moitié de gauche : comme le tableau est trié par ordre croissant, toutes les valeurs à gauche sont encore plus petites. Sans tri, cette élimination n'aurait aucune justification et tu risquerais de jeter la case qui contient la réponse.

ExempleUn exemple à la main

On cherche 34 dans le tableau trié [3, 8, 12, 15, 21, 27, 34, 40, 52, 61] (indices de 0 à 9).

Tour	Zone (indices)	Milieu	Valeur au milieu	Décision
1	0 à 9	4	21	21 < 34 : on garde la droite, indices 5 à 9
2	5 à 9	7	40	40 > 34 : on garde la gauche, indices 5 à 6
3	5 à 6	5	27	27 < 34 : on garde la droite, indice 6
4	6 à 6	6	34	égalité : la valeur est à l'indice 6

Le tableau avait 10 cases et il a suffi de 4 comparaisons. Avec un parcours séquentiel, il en aurait fallu 7.

Calculer le milieum = (g + d) // 2
ComparerComparer tab[m] à la valeur x
Choisir une moitiéTrop petit : g = m + 1. Trop grand : d = m - 1
Recommencer ou finirÉgalité : renvoyer m. Zone vide : absent

Les étapes d'un tour de dichotomie · Un tour de boucle de la recherche dichotomique.

L'algorithme en Python

Pour représenter la zone de recherche, on utilise deux indices : g (gauche) est l'indice de la première case encore possible, d (droite) celui de la dernière. La zone est donc l'ensemble des cases d'indices compris entre g et d, bornes incluses. Au départ, c'est tout le tableau.

MéthodeÉcrire la fonction

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

On initialise la zone à tout le tableau : g = 0, d = len(tab) - 1.
Tant que la zone n'est pas vide (g <= d), on calcule le milieu m avec une division entière.
Si tab[m] vaut x, on renvoie m.
Si tab[m] est trop petit, la valeur ne peut être qu'à droite : g = m + 1.
Sinon, elle ne peut être qu'à gauche : d = m - 1.
Si la zone devient vide, la valeur est absente : on renvoie None.

Observe m + 1 et d - 1 : on retire aussi la case du milieu, puisqu'on vient de la tester. C'est ce qui garantit que la zone rétrécit à chaque tour, ce qu'on exploitera pour prouver l'arrêt.

La boucle est une boucle non bornée : on ne sait pas à l'avance combien de tours auront lieu, contrairement à une boucle for. Pour être sûr que la fonction rend toujours la main, il faut donc une preuve de terminaison.²

Pourquoi l'algorithme s'arrête : le variant

Une boucle while peut ne jamais s'arrêter. Pour prouver qu'elle s'arrête, on cherche une quantité entière, positive tant qu'on reste dans la boucle, qui diminue strictement à chaque tour. Une telle quantité s'appelle un variant de boucle. Comme il n'existe pas de suite infinie strictement décroissante d'entiers naturels, la boucle finit forcément par s'arrêter.²

Démonstration · Terminaison de la recherche dichotomique

Prenons comme variant la taille de la zone : $v = d - g + 1$ . Tant que la condition g <= d est vraie, on a $v \geq 1$ .

Au cours d'un tour, avec $m = \lfloor (g+d)/2 \rfloor$ , on a $g \leq m \leq d$ . Trois cas :

si tab[m] == x, on sort de la boucle avec return ;
si tab[m] < x, le nouvel indice de gauche est $m+1 > m \geq g$ ; d ne change pas, donc $d - (m+1) + 1 = d - m \leq d - g$ , qui est strictement inférieur à $d - g + 1$ ;
si tab[m] > x, le nouvel indice de droite est $m-1 < m \leq d$ ; g ne change pas, donc $(m-1) - g + 1 = m - g \leq d - g < d - g + 1$ .

Dans tous les cas, $v$ diminue strictement. Comme $v$ est un entier et reste supérieur ou égal à 1 tant qu'on boucle, la boucle s'arrête après un nombre fini de tours.

Pourquoi le résultat est correct : l'invariant

Pour la recherche dichotomique, l'invariant naturel est la phrase suivante : si la valeur x est dans le tableau, alors elle se trouve dans la zone d'indices de g à d. Autrement dit, on n'a jamais éliminé la bonne case par erreur. On suppose que le tableau est trié par ordre croissant.

Démonstration · Preuve de l'invariant

Initialisation. Avant la boucle, $g = 0$ et $d =$ len(tab) - 1 : la zone est le tableau entier. Si x est dans le tableau, il est bien dans la zone.

Conservation. Supposons l'invariant vrai au début d'un tour et x présent dans le tableau, donc dans la zone $[g\,;\,d]$ .

Si tab[m] < x, comme le tableau est trié, toutes les cases d'indices inférieurs ou égaux à $m$ contiennent des valeurs inférieures ou égales à tab[m], donc strictement inférieures à x. La valeur x ne peut donc pas s'y trouver ; elle est dans $[m+1\,;\,d]$ , qui est la nouvelle zone.
Si tab[m] > x, de même toutes les cases d'indices supérieurs ou égaux à $m$ contiennent des valeurs strictement supérieures à x ; la valeur est dans $[g\,;\,m-1]$ , la nouvelle zone.

L'invariant reste donc vrai.

Conclusion. Il y a deux façons de sortir de la boucle.

Par return m : on a tab[m] == x, l'indice renvoyé est correct.
Parce que $g > d$ : la zone est vide. Si x était dans le tableau, l'invariant dirait qu'il est dans une zone vide, ce qui est absurde. Donc x n'est pas dans le tableau, et renvoyer None est correct.

Le coût : un nombre de tours logarithmique

On mesure le coût d'un algorithme par le nombre d'opérations élémentaires en fonction de la taille $n$ des données. Ici, on compte surtout le nombre de comparaisons, c'est-à-dire de tours de boucle. Le nombre de tours est logarithmique en la taille du tableau.³

Intuitivement : à chaque tour, la zone est divisée par 2. Combien de fois peut-on diviser $n$ par 2 avant d'arriver à une zone de taille 1 ? C'est la question que pose le logarithme en base 2. Avec 8 éléments : $8 \to 4 \to 2 \to 1$ , trois divisions et $\log_2(8) = 3$ .

Démonstration · Majoration du nombre de divisions

On note $k$ le nombre de tours effectués (un entier naturel non nul) et $n$ la taille initiale. La taille de la zone est divisée par 2 à chaque itération, donc après $k$ tours elle vaut $\lfloor n / 2^k \rfloor$ (partie entière).³ Pour que la boucle ait effectué ces $k$ divisions, la taille ne peut pas être descendue sous 1 :

$1 \leq \frac{n}{2^k}$

En multipliant par $2^k > 0$ : $2^k \leq n$ . La fonction logarithme décimal étant croissante : $k \log(2) \leq \log(n)$ . En divisant par $\log(2) > 0$ :

$k \leq \frac{\log(n)}{\log(2)} = \log_2(n)$

On en déduit que le nombre de divisions successives est au plus $\log_2(n)$ .³

Nombre de divisions par 2 selon la taille du tableau
Taille n	Pire cas séquentiel	Divisions par 2 (dichotomie)
8	8	3
16	16	4
1 000	1 000	9
1 000 000	1 000 000	19
1 000 000 000	1 000 000 000	29

Nombre de divisions par 2 selon la taille du tableau · Les nombres de divisions sont les parties entières de log2(n).

Le tableau ci-dessus donne l'ordre de grandeur pour quelques tailles. Pour un milliard de cases, une trentaine de tours suffisent au pire. C'est ce qui rend la méthode si puissante sur de grandes données. Les valeurs du tableau sont obtenues en calculant la partie entière de $\log_2(n)$ ; au pire, il faut un tour de plus pour tester la zone finale de taille 1.

Quand l'utiliser ? Comparaison avec les autres recherches

Parmi les méthodes de recherche, la recherche séquentielle est la plus élémentaire : son temps de calcul est linéaire, puisqu'on regarde les éléments l'un après l'autre. Elle ne réclame aucun tri préalable, et on peut l'employer aussi bien sur un tableau que sur une liste chaînée, structure parfois mieux adaptée à certains besoins.³

Sur des tableaux ordonnés, la dichotomie gagne à partir d'une certaine taille, mais l'avantage n'est pas garanti sur de petits tableaux.³ Quand il n'y a que quelques éléments, calculer le milieu et enchaîner les comparaisons peut coûter autant qu'un simple parcours.

Critère	Recherche séquentielle	Recherche dichotomique
Tableau trié nécessaire	non³	oui
Nombre de comparaisons	linéaire³	logarithmique³
Fonctionne sur une liste chaînée	oui³	peu adaptée : accès au milieu coûteux
Petit tableau	souvent suffisante³	pas forcément plus rapide³

D'autres structures répondent plus vite. Le hachage est en général plus rapide : son coût amorti ne dépend pas de la taille. La dichotomie garde pourtant un atout, sa souplesse : elle rend d'autres services qu'une recherche exacte, par exemple retrouver les éléments les plus proches d'une valeur donnée.³

Enfin, les arbres binaires de recherche reposent sur un partage en deux comparable. Insérer ou supprimer un élément y coûte un temps logarithmique, contre un temps linéaire dans un tableau trié, mais ils occupent davantage de mémoire. Et lorsqu'un tel arbre est mal équilibré, la dichotomie sur tableau est plus rapide.³ Tu les retrouveras dans le programme de NSI, en lien avec les types abstraits de données.¹

Méthode et pièges pour réussir à l'écrit

Exercices corrigés

Exercice 1 Dérouler l'algorithme à la main

★☆☆Environ 8 min

On considère le tableau trié T = [2, 5, 9, 14, 20, 26, 31, 38, 45, 59, 64] (indices de 0 à 10) et la fonction recherche_dichotomique du cours.

On cherche la valeur 38. Donne l'indice renvoyé.

Indice 1

Au départ, g = 0 et d = 10.

Indice 2

Calcule m = (g + d) // 2 puis compare T[m] à 38.

Voir la correction pas à pas

Tour 1 : g = 0, d = 10, m = 5, T[5] = 26. Comme 26 < 38, on pose g = 6.
Tour 2 : g = 6, d = 10, m = 8, T[8] = 45. Comme 45 > 38, on pose d = 7.
Tour 3 : g = 6, d = 7, m = 6, T[6] = 31. Comme 31 < 38, on pose g = 7.
Tour 4 : g = 7, d = 7, m = 7, T[7] = 38. Égalité : la fonction renvoie 7.

La valeur 38 se trouve à l'indice 7, trouvée en 4 comparaisons sur un tableau de 11 éléments. Un parcours séquentiel en aurait demandé 8.

Exercice 2 Combien de tours au maximum ?

★★☆Environ 10 min

Un annuaire numérique contient $n = 1\,000\,000$ numéros triés dans un tableau. On suppose que la taille de la zone de recherche est divisée par 2 à chaque tour, avec partie entière.

Quelle inégalité vérifie le nombre $k$ de divisions successives ?
Donne la plus grande valeur entière possible de $k$ .
Compare avec le nombre de comparaisons d'un parcours séquentiel dans le pire cas.

Indice 1

Utilise $k \leq \log_2(n)$ .

Indice 2

Encadre $n$ par deux puissances de 2 : $2^{19} = 524\,288$ et $2^{20} = 1\,048\,576$ .

Voir la correction pas à pas

Après $k$ divisions, la taille vaut $\lfloor n/2^k \rfloor$ , qui doit rester supérieure ou égale à 1. On obtient $2^k \leq n$ , donc $k \leq \log_2(n)$ .
Ici $2^{19} = 524\,288 \leq 1\,000\,000 < 1\,048\,576 = 2^{20}$ , donc $\log_2(10^6)$ est compris entre 19 et 20, et la plus grande valeur entière de $k$ est 19.
Au pire, la recherche dichotomique effectue de l'ordre de 20 comparaisons (19 divisions plus le test de la zone finale), contre 1 000 000 pour un parcours séquentiel.

Pour un million d'éléments, une vingtaine de comparaisons suffisent : le rapport avec un million de comparaisons montre pourquoi on parle de complexité logarithmique face à la complexité linéaire.

Exercice 3 Trouver l'erreur dans une fonction

★★★Environ 15 min

Un élève propose cette fonction :

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

Avec tab = [1, 3] et x = 3, que se passe-t-il ? Explique.
Avec tab = [4] et x = 4, que renvoie la fonction ? Est-ce correct ?
Corrige la fonction et propose un variant.

Indice 1

Fais un tableau de suivi de g, d, m pas à pas.

Indice 2

Compare avec la version du cours : condition de boucle et mises à jour de g et d.

Voir la correction pas à pas

Avec [1, 3] et x = 3 : g = 0, d = 1, m = 0, tab[0] = 1 < 3, donc g = m = 0. Rien n'a changé : on recommence avec la même zone, à l'infini. Le programme ne s'arrête jamais, car la zone ne rétrécit pas.
Avec [4] et x = 4 : g = 0 et d = 0, la condition g < d est fausse dès le départ. La fonction renvoie None alors que 4 est présent : le résultat est faux.
Correction : remplacer while g < d par while g <= d, g = m par g = m + 1, et d = m par d = m - 1.
Variant : la taille de la zone $d - g + 1$ est un entier supérieur ou égal à 1 dans la boucle et diminue strictement à chaque tour, ce qui prouve la terminaison.

Deux erreurs différentes produisent deux bugs différents : des mises à jour sans +1 ou -1 empêchent l'arrêt (terminaison), une mauvaise condition de boucle écarte un cas (correction). Il faut vérifier les deux propriétés.

Les questions qu'on se pose

Pourquoi le tableau doit-il être trié ?

Parce que l'algorithme élimine une moitié du tableau sans la regarder. Cette élimination n'est légitime que si l'on sait que les valeurs d'un côté du milieu sont toutes plus petites, et celles de l'autre côté toutes plus grandes. Sur un tableau non trié, tu pourrais écarter la case qui contient la valeur et répondre « absent » à tort.³

La dichotomie est-elle toujours plus rapide que la recherche séquentielle ?

Non. Elle est plus rapide asymptotiquement, c'est-à-dire sur de grands tableaux, mais pas forcément sur de petits tableaux.³ De plus, si le tableau n'est pas trié, il faut d'abord le trier, ce qui a un coût. Elle est vraiment intéressante quand on fait de nombreuses recherches sur un tableau déjà trié.

Quelle est la différence entre un variant et un invariant ?

Le variant sert à prouver que la boucle s'arrête : c'est un entier qui décroît strictement à chaque tour.² L'invariant sert à prouver que le résultat est correct : c'est une propriété vraie avant la boucle, conservée à chaque tour et vraie à la sortie.² Les deux sont nécessaires pour justifier une fonction complète.

Comment calculer le nombre maximal de tours pour n éléments ?

Le nombre de divisions par 2 est au plus $\log_2(n)$ .³ En pratique, tu calcules la plus grande puissance de 2 inférieure ou égale à $n$ : si $2^k \leq n < 2^{k+1}$ , alors il y a au plus $k$ divisions, et environ $k+1$ comparaisons en comptant le test de la dernière zone. Par exemple pour $n = 1000$ , $2^9 = 512 \leq 1000 < 1024 = 2^{10}$ , donc 9 divisions.

Que renvoie la fonction quand la valeur n'est pas dans le tableau ?

Quand la zone de recherche devient vide, cela signifie que la valeur n'est pas présente.² La fonction doit alors renvoyer une valeur convenue à l'avance, comme None. Évite -1 : en Python, -1 est un indice valide qui désigne la dernière case, ce qui peut prêter à confusion. À l'examen, indique clairement ta convention.

Quel rapport avec les arbres binaires de recherche ?

Un arbre binaire de recherche reprend l'idée de la dichotomie : à chaque nœud, on choisit de descendre à gauche ou à droite, ce qui écarte une partie des valeurs.³ Son atout est le coût logarithmique de l'insertion et de la suppression, alors qu'un tableau trié impose un coût linéaire.³ Ces arbres figurent au programme de NSI.¹

Sources

Programme visé : Programmes et ressources en numérique et sciences informatiques — Voie générale (Première) · Éduscol (Ministère de l'Éducation Nationale)

Programmes et ressources en numérique et sciences informatiques — Voie générale (Première), Éduscol (Ministère de l'Éducation Nationale). Consulté le 6 novembre 2026.
Ressources pédagogiques — Recherche dichotomique et algorithmique, Éduscol. Consulté le 6 novembre 2026.
Recherche dichotomique, Wikipédia. Consulté le 6 novembre 2026.
Dichotomie, Wikipédia. Consulté le 6 novembre 2026.

Les numéros dans le texte renvoient à ces sources. Une source qui ne dit pas ce qu'on lui fait dire ? Signale-le.

Signaler une erreur sur cette page

La recherche dichotomique : cours de NSI en Première

L'essentiel

Pourquoi chercher mieux qu'élément par élément ?

Le principe de la dichotomie

L'algorithme en Python

Pourquoi l'algorithme s'arrête : le variant

Pourquoi le résultat est correct : l'invariant

Le coût : un nombre de tours logarithmique

Quand l'utiliser ? Comparaison avec les autres recherches

Méthode et pièges pour réussir à l'écrit

Exercices corrigés

Exercice 1 Dérouler l'algorithme à la main

Exercice 2 Combien de tours au maximum ?

Exercice 3 Trouver l'erreur dans une fonction

Quiz

Les questions qu'on se pose

Sources

Primaire

Collège

Lycée

Supérieur