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

Recherche dichotomique : exercices corrigés de NSI Première

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

L'essentiel

La recherche dichotomique s'applique à un tableau trié : on compare la valeur du milieu à la valeur cherchée, puis on garde la moitié pertinente ³.
À chaque tour, l'intervalle de recherche est coupé en deux, ce qui rend le nombre de comparaisons logarithmique en la taille du tableau ²³.
La boucle while s'arrête quand la valeur est trouvée ou quand l'intervalle devient vide ; le variant garantit cet arrêt, l'invariant garantit la correction ².
Pour s'entraîner : tracer l'algorithme à la main, calculer un milieu, estimer un coût, écrire la fonction, repérer un bug et justifier variant et invariant.

Comment utiliser ces exercices

Ces exercices te font manipuler la recherche dichotomique, de la simple trace à la main jusqu'à la justification d'un variant et d'un invariant. Fais-les dans l'ordre : la difficulté monte progressivement, et chaque exercice réutilise un réflexe de l'exercice précédent. Prends une feuille, écris toi-même les valeurs de debut, fin et milieu à chaque tour, et ne regarde les indices qu'après avoir cherché quelques minutes.

Les exercices

Exercice 1 Trace d'une recherche réussie

★☆☆Environ 8 min

On considère le tableau trié

tab = [3, 8, 12, 17, 21, 26, 30, 35, 41]

de 9 cases, indexées de 0 à 8. On cherche la valeur x = 26 par recherche dichotomique, avec milieu = (debut + fin) // 2.

Déroule l'algorithme en notant debut, fin, milieu et tab[milieu] à chaque tour.
Donne l'indice auquel la valeur 26 est trouvée.
Combien de tours de boucle ont été nécessaires ?

Indice 1

Au départ, debut vaut 0 et fin vaut 8 : calcule d'abord le milieu avec la division entière.

Indice 2

Si tab[milieu] est plus petit que 26, la valeur est dans la moitié droite : debut devient milieu + 1.

Voir la correction pas à pas

Tour 1 : debut = 0, fin = 8, donc milieu = 4. On lit tab[4] = 21. Comme 21 < 26, la valeur cherchée est à droite : debut = 5.
Tour 2 : debut = 5, fin = 8, donc milieu = (5 + 8) // 2 = 6. On lit tab[6] = 30. Comme 30 > 26, la valeur cherchée est à gauche : fin = 5.
Tour 3 : debut = 5, fin = 5, donc milieu = 5. On lit tab[5] = 26, ce qui est égal à x : la recherche s'arrête.
Réponse : la valeur 26 se trouve à l'indice 5, après 3 tours de boucle.

Sur 9 cases, trois lectures ont suffi, alors qu'un parcours séquentiel en aurait demandé 6 pour atteindre cette case. Remarque que l'intervalle s'est réduit à une seule case au dernier tour : c'est le cas que ta condition de boucle doit absolument accepter.

Exercice 2 Calculer un milieu

★☆☆Environ 4 min

Au cours d'une recherche dichotomique, les variables valent debut = 10 et fin = 21.

Calcule milieu = (debut + fin) // 2.
Le tableau est trié par ordre croissant et on constate que tab[milieu] est strictement inférieur à la valeur cherchée. Quelles sont alors les nouvelles valeurs de debut et de fin, puis le nouveau milieu ?

Indice 1

L'opérateur // donne le quotient entier : 31 divisé par 2 donne 15 et non 15,5.

Indice 2

Si la valeur du milieu est trop petite, la valeur cherchée est après la case du milieu.

Voir la correction pas à pas

On additionne : 10 + 21 = 31.
On prend le quotient entier de 31 par 2 : 31 // 2 = 15. Le milieu vaut donc 15.
La valeur lue est trop petite et le tableau est croissant : la valeur cherchée, si elle existe, est à droite de la case 15. On exclut la case 15 : debut = 16, et fin reste égal à 21.
Nouveau milieu : (16 + 21) // 2 = 37 // 2 = 18.

L'intervalle est passé de 12 cases (de 10 à 21) à 6 cases (de 16 à 21) : il a bien été divisé par deux. Quand la somme est impaire, la division entière arrondit vers le bas, ce qui n'a aucune conséquence sur la correction de l'algorithme.

Exercice 3 Une valeur absente

★☆☆Environ 8 min

On cherche x = 10 dans le tableau trié

tab = [2, 5, 9, 14, 20, 27]

(indices de 0 à 5), avec la boucle while debut <= fin.

Déroule l'algorithme jusqu'à son arrêt.
Quelle condition provoque l'arrêt, et que peut-on en conclure ?

Indice 1

Avant chaque tour, vérifie que debut est encore inférieur ou égal à fin.

Indice 2

Quand fin devient plus petit que debut, il ne reste plus aucune case à examiner.

Voir la correction pas à pas

Tour 1 : debut = 0, fin = 5, milieu = 2. On lit tab[2] = 9. Comme 9 < 10, on pose debut = 3.
Tour 2 : debut = 3, fin = 5, milieu = 4. On lit tab[4] = 20. Comme 20 > 10, on pose fin = 3.
Tour 3 : debut = 3, fin = 3, milieu = 3. On lit tab[3] = 14. Comme 14 > 10, on pose fin = 2.
Avant le tour 4, on teste debut <= fin : 3 <= 2 est faux, la boucle s'arrête.
Conclusion : l'intervalle de recherche est vide, la valeur 10 n'est pas dans le tableau. La fonction renvoie donc le résultat prévu pour une valeur absente.

Une recherche qui échoue se termine quand l'intervalle devient vide, pas quand on a lu toutes les cases. Ici, 3 lectures ont suffi pour prouver l'absence de 10 dans un tableau de 6 valeurs. Retiens que le résultat « valeur absente » est lui aussi une réponse précise de l'algorithme ².

Exercice 4 Quand le tableau n'est pas trié

★★☆Environ 8 min

Léa applique la recherche dichotomique au tableau

tab = [5, 1, 9, 3, 7]

(indices de 0 à 4) pour chercher x = 3, alors que 3 est bien présent à l'indice 3.

Déroule l'algorithme tel que Léa l'a écrit, avec while debut <= fin.
Quel résultat obtient-elle ? Explique pourquoi il est faux.
Quelle condition sur le tableau Léa a-t-elle oublié de vérifier ?

Indice 1

Applique mécaniquement les règles : tab[milieu] > x entraîne fin = milieu - 1.

Indice 2

Demande-toi ce qui permet d'affirmer que la valeur n'est pas dans la moitié que l'on écarte.

Voir la correction pas à pas

Tour 1 : debut = 0, fin = 4, milieu = 2. On lit tab[2] = 9. Comme 9 > 3, on pose fin = 1.
Tour 2 : debut = 0, fin = 1, milieu = 0. On lit tab[0] = 5. Comme 5 > 3, on pose fin = -1.
Avant le tour 3, debut <= fin s'écrit 0 <= -1 : faux. La boucle s'arrête et la fonction répond que 3 est absent.
Ce résultat est faux : 3 est en case 3. À l'étape 1, on a écarté la moitié droite en pensant que tout y était supérieur à 9, ce qui est faux ici puisque 3 s'y trouve.
Léa a oublié que la recherche dichotomique ne fonctionne que sur un tableau trié ³. L'argument « tout ce qui est à droite est plus grand » n'est valable que si le tableau est croissant.

La comparaison avec la case du milieu ne donne une information sur toute une moitié du tableau que si le tableau est trié. À l'inverse, la recherche séquentielle n'exige pas de structure triée ³ : sur un tableau non trié, c'est elle qu'il faut utiliser, ou bien trier d'abord.

Exercice 5 Combien de tours pour 1000 valeurs ?

★★☆Environ 10 min

À chaque tour de boucle, la taille de l'intervalle de recherche est environ divisée par 2 ³. On cherche une valeur dans un tableau trié de $n = 1000$ cases, dans le pire des cas (la valeur est absente, ou trouvée tout à la fin).

Écris la suite des tailles de l'intervalle d'un tour à l'autre, en arrondissant à l'entier inférieur à chaque division par 2, jusqu'à arriver à une taille de 1.
En déduire le nombre maximal de tours de boucle.
Vérifie ce résultat avec une puissance de 2.

Indice 1

Pars de 1000 et divise par 2 en gardant la partie entière : 1000, 500, 250, ...

Indice 2

Cherche la plus grande puissance de 2 inférieure ou égale à 1000, puis ajoute 1.

Voir la correction pas à pas

Suite des tailles : 1000, 500, 250, 125, 62, 31, 15, 7, 3, 1.
Chaque taille correspond à un tour de boucle (le dernier tour traite l'intervalle d'une seule case). On compte 10 tailles, donc 10 tours au maximum.
Vérification : $2^9 = 512 \leq 1000 < 1024 = 2^{10}$ . La partie entière de $\log_2(1000)$ vaut 9, et on ajoute 1 pour le dernier tour : $9 + 1 = 10$ .
Réponse : au plus 10 tours, soit 10 comparaisons, pour un tableau de 1000 cases.

Le nombre de comparaisons est logarithmique en la taille du tableau ³ : pour 1000 cases, une dizaine de tours suffit, là où un parcours séquentiel peut en demander 1000. Tu retrouves au passage l'idée du raisonnement de la source : si $k$ tours sont effectués, la taille finale étant au moins 1, on obtient $2^k \leq n$ puis $k \leq \log_2(n)$ ³.

Exercice 6 Un million de cases

★★☆Environ 10 min

Un tableau trié contient $n = 1\,000\,000$ valeurs. On compare deux méthodes dans le pire des cas.

Combien de comparaisons demande une recherche séquentielle, qui examine les éléments les uns après les autres ³ ?
Combien de tours de boucle au maximum pour une recherche dichotomique ? Utilise les puissances de 2.
Compare les deux résultats en une phrase.

Indice 1

Calcule les puissances de 2 successives : $2^{10} = 1024$ , puis double encore.

Indice 2

Le dernier tour traite un intervalle d'une seule case : ajoute 1 à la partie entière du logarithme.

Voir la correction pas à pas

Recherche séquentielle : au pire, on examine les 1 000 000 cases, soit 1 000 000 comparaisons.
Puissances de 2 : $2^{10} = 1024$ , donc $2^{20} = 1024 \times 1024 = 1\,048\,576$ et $2^{19} = 524\,288$ .
On a $2^{19} \leq 1\,000\,000 < 2^{20}$ : la partie entière de $\log_2(1\,000\,000)$ vaut 19.
Nombre maximal de tours : $19 + 1 = 20$ .
Comparaison : 20 comparaisons contre 1 000 000, soit 50 000 fois moins.

Plus le tableau est grand, plus l'écart est spectaculaire : c'est la différence entre un temps linéaire (la recherche séquentielle) et un temps logarithmique (la dichotomie) ³. Garde néanmoins en tête que sur des tableaux de petite taille, la dichotomie n'est pas forcément plus rapide en pratique ³.

Exercice 7 Écrire la fonction de recherche

★★☆Environ 15 min

Écris en Python une fonction recherche_dichotomique(tab, x) qui prend un tableau trié par ordre croissant tab et une valeur x, et qui renvoie l'indice d'une case contenant x, ou None si x n'est pas dans le tableau.

Contraintes : utilise une boucle while, trois variables debut, fin et milieu, et ne parcours jamais tout le tableau.

Teste ensuite ta fonction à la main sur tab = [1, 4, 6, 9] avec x = 9, puis avec x = 5.

Indice 1

Commence par initialiser debut à 0 et fin à len(tab) - 1.

Indice 2

Dans la boucle, il y a trois cas : égalité, valeur du milieu trop petite, valeur du milieu trop grande. N'oublie pas le return None après la boucle.

Voir la correction pas à pas

Initialisation : debut = 0 et fin = len(tab) - 1, de sorte que l'intervalle couvre tout le tableau.
Condition de boucle : while debut <= fin, pour continuer tant qu'il reste au moins une case à examiner.
Dans la boucle, on calcule milieu = (debut + fin) // 2, puis on traite les trois cas : tab[milieu] == x renvoie milieu ; tab[milieu] < x pose debut = milieu + 1 ; sinon fin = milieu - 1.
Après la boucle, on renvoie None, puisque l'intervalle est vide.
Test avec x = 9 : tour 1, milieu = 1, tab[1] = 4 < 9, donc debut = 2 ; tour 2, milieu = (2 + 3) // 2 = 2, tab[2] = 6 < 9, donc debut = 3 ; tour 3, milieu = 3, tab[3] = 9 : on renvoie 3.
Test avec x = 5 : tour 1, milieu = 1, 4 < 5, donc debut = 2 ; tour 2, milieu = 2, 6 > 5, donc fin = 1 ; 2 <= 1 est faux, on sort de la boucle et on renvoie None.

Voici une version complète :

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

Le choix de renvoyer None pour une valeur absente est une convention de cet exercice ; d'autres sont possibles tant qu'elles sont documentées. La fonction renvoie bien l'un des deux comportements attendus : un indice valide, ou le signal que la valeur est absente ².

Exercice 8 Trouver le bug

★★★Environ 12 min

Un élève propose cette version :

def recherche(tab, x):
    debut = 0
    fin = len(tab) - 1
    while debut < fin:
        milieu = (debut + fin) // 2
        if tab[milieu] == x:
            return milieu
        elif tab[milieu] < x:
            debut = milieu + 1
        else:
            fin = milieu - 1
    return None

Trace l'appel recherche([2, 4, 6], 6). Que renvoie la fonction ? Est-ce correct ?
Trouve un second tableau, le plus petit possible, pour lequel la fonction se trompe aussi.
Corrige l'erreur et explique en une phrase pourquoi la correction fonctionne.

Indice 1

Regarde ce qui se passe quand debut et fin deviennent égaux : la boucle est-elle exécutée ?

Indice 2

Un tableau d'une seule case peut suffire à faire échouer la fonction.

Voir la correction pas à pas

Appel recherche([2, 4, 6], 6) : debut = 0, fin = 2, la condition 0 < 2 est vraie, milieu = 1, tab[1] = 4 < 6, donc debut = 2.
Retour au test de la boucle : debut < fin s'écrit 2 < 2, c'est faux. La boucle s'arrête et la fonction renvoie None, alors que 6 est présent à l'indice 2 : le résultat est faux.
Le défaut est la condition debut < fin : quand l'intervalle est réduit à une seule case (debut == fin), cette case n'est jamais examinée.
Plus petit contre-exemple : recherche([7], 7). Ici debut = 0 et fin = 0, la boucle ne s'exécute pas et la fonction renvoie None alors que 7 est bien dans le tableau.
Correction : remplacer while debut < fin par while debut <= fin. L'intervalle tab[debut..fin] est alors considéré comme vide seulement quand debut > fin, et une case unique est toujours examinée.

Cette erreur est l'une des plus courantes, parce qu'elle ne se voit pas sur la plupart des tests : elle n'apparaît que lorsque la valeur cherchée se trouve dans le dernier intervalle d'une seule case. Pense toujours à tester les cas limites : tableau d'une case, valeur en première case, valeur en dernière case, valeur absente.

Exercice 9 Variant : la boucle s'arrête-t-elle ?

★★★Environ 12 min

Pour prouver qu'une boucle while se termine, on cherche un variant : une quantité entière qui décroît strictement à chaque tour tout en restant positive ou nulle tant que la boucle continue. Cette notion de variant est justement utilisée pour la boucle while de la recherche dichotomique ².

On reprend la version correcte de la fonction (avec while debut <= fin). On pose $v = \text{fin} - \text{debut} + 1$ , le nombre de cases de l'intervalle.

Montre que, si la boucle ne s'arrête pas par un return, la valeur de $v$ diminue strictement à chaque tour.
Pour un tableau de $n = 16$ cases, écris les valeurs successives de $v$ dans le pire des cas, en prenant à chaque fois la moitié la plus grande, et donne le nombre maximal de tours.

Indice 1

Distingue deux cas : on met à jour debut, ou on met à jour fin. Dans chacun, exprime la nouvelle valeur de v.

Indice 2

Pour n = 16 avec debut = 0 et fin = 15, calcule milieu = 7 et regarde la taille de chaque moitié.

Voir la correction pas à pas

Cas debut = milieu + 1 : comme milieu >= debut, le nouveau debut est au moins debut + 1, donc $v$ diminue d'au moins 1.
Cas fin = milieu - 1 : comme milieu <= fin, la nouvelle valeur de fin est au plus fin - 1, donc $v$ diminue aussi d'au moins 1.
Tant que la boucle continue, on a debut <= fin, donc $v \geq 1$ : c'est un entier naturel non nul. Un entier naturel ne peut pas décroître strictement indéfiniment, donc la boucle se termine.
Pire cas pour $n = 16$ : l'intervalle de départ est de 0 à 15, milieu = 7. La moitié gauche (cases 0 à 6) compte 7 cases, la moitié droite (cases 8 à 15) en compte 8. On prend la plus grande : $v = 8$ .
Intervalle de 8 à 15, milieu = 11, moitié droite de 12 à 15 : $v = 4$ . Puis intervalle de 12 à 15, milieu = 13, moitié droite de 14 à 15 : $v = 2$ . Puis intervalle de 14 à 15, milieu = 14, moitié droite de 15 à 15 : $v = 1$ .
Suite des valeurs de $v$ au début de chaque tour : 16, 8, 4, 2, 1. Cela fait 5 tours au maximum.

Le variant prouve seulement que la boucle s'arrête : comme l'indique la ressource Éduscol, une utilisation très basique du variant ne suffit pas, telle quelle, à justifier la complexité de la recherche dichotomique ². Pour cela, il faut remarquer que $v$ est divisé par 2 environ à chaque tour, ce qui donne un nombre de tours de l'ordre de $\log_2(n)$ ³.

Exercice 10 Invariant : la fonction est-elle correcte ?

★★★Environ 15 min

Un invariant de boucle est une propriété vraie avant la boucle, qui reste vraie après chaque tour, et qui permet de conclure à la sortie de la boucle. La ressource Éduscol prouve que la fonction de recherche dichotomique possède un tel invariant ².

On reprend la version correcte de la fonction et le tableau tab trié par ordre croissant. On propose l'invariant suivant :

« Si la valeur x est dans tab, alors elle est dans la partie tab[debut..fin]. »

Vérifie que cette propriété est vraie avant le premier tour.
Montre qu'elle reste vraie après un tour dans lequel tab[milieu] < x, puis après un tour dans lequel tab[milieu] > x.
Utilise l'invariant, à la sortie de la boucle sans return, pour justifier que renvoyer None est correct.

Indice 1

Avant le premier tour, quelle partie du tableau est désignée par tab[0..len(tab)-1] ?

Indice 2

Pour la question 2, utilise le fait que le tableau est trié : que sait-on des cases situées à gauche du milieu quand tab[milieu] < x ?

Voir la correction pas à pas

Initialisation : avant la boucle, debut = 0 et fin = len(tab) - 1, donc tab[debut..fin] est le tableau tout entier. Si x est dans tab, il est bien dans cette partie : l'invariant est vrai.
Conservation, cas tab[milieu] < x : comme le tableau est croissant, toutes les cases de debut à milieu contiennent des valeurs inférieures ou égales à tab[milieu], donc strictement inférieures à x. Si x est dans tab[debut..fin], il est donc dans tab[milieu+1..fin]. Avec debut = milieu + 1, l'invariant reste vrai.
Conservation, cas tab[milieu] > x : toutes les cases de milieu à fin contiennent des valeurs supérieures ou égales à tab[milieu], donc strictement supérieures à x. Si x est dans tab[debut..fin], il est dans tab[debut..milieu-1]. Avec fin = milieu - 1, l'invariant reste vrai.
Sortie sans return : la condition debut <= fin est fausse, donc debut > fin et la partie tab[debut..fin] est vide. Si x était dans tab, il serait dans cette partie vide, ce qui est impossible. Donc x n'est pas dans tab, et renvoyer None est correct.
Sortie par return milieu : on a tab[milieu] == x, l'indice renvoyé est donc bien celui d'une case contenant x.

Tu viens de démontrer que la fonction a deux comportements possibles et que chacun est correct : soit elle renvoie un indice valide, soit elle signale que la valeur n'est pas présente ². Remarque où intervient l'hypothèse « tableau trié » : uniquement dans la conservation de l'invariant, ce qui explique pourquoi tout casse sur un tableau non trié.

Les questions qu'on se pose

Pourquoi le tableau doit-il être trié pour une recherche dichotomique ?

Parce que l'algorithme compare la valeur cherchée à celle du milieu pour décider de la moitié à garder ³. Cette décision n'est valable que si les valeurs sont rangées dans l'ordre : dans un tableau croissant, tout ce qui est à gauche du milieu est inférieur ou égal à la valeur du milieu, tout ce qui est à droite est supérieur ou égal. Sans cela, on peut écarter la moitié qui contient la valeur, comme dans l'exercice sur le tableau non trié. La recherche séquentielle, elle, ne demande pas de tableau trié ³.

La recherche dichotomique est-elle toujours plus rapide qu'une recherche séquentielle ?

Pas toujours. Sur un grand tableau trié, elle est nettement plus rapide : son nombre de comparaisons est logarithmique, contre un temps linéaire pour la recherche séquentielle ³. En revanche, sur des tableaux de petite taille, la dichotomie n'est pas forcément plus rapide ³. Il faut aussi que le tableau soit déjà trié : si tu dois le trier uniquement pour faire une recherche, le coût du tri est à prendre en compte.

Dans un exercice, comment éviter les erreurs de bornes (debut, fin, milieu) ?

Fais systématiquement un tableau de trace avec les colonnes debut, fin, milieu, tab[milieu], et exclus toujours la case du milieu après l'avoir examinée (milieu + 1 ou milieu - 1). Puis teste trois cas limites : un tableau d'une seule case, une valeur située à l'une des extrémités, et une valeur absente. Ces trois tests révèlent presque toutes les erreurs de bornes, notamment la condition debut < fin au lieu de debut <= fin.

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

Recherche dichotomique : exercices corrigés de NSI Première

L'essentiel

Comment utiliser ces exercices

Les exercices

Exercice 1 Trace d'une recherche réussie

Exercice 2 Calculer un milieu

Exercice 3 Une valeur absente

Exercice 4 Quand le tableau n'est pas trié

Exercice 5 Combien de tours pour 1000 valeurs ?

Exercice 6 Un million de cases

Exercice 7 Écrire la fonction de recherche

Exercice 8 Trouver le bug

Exercice 9 Variant : la boucle s'arrête-t-elle ?

Exercice 10 Invariant : la fonction est-elle correcte ?

Les questions qu'on se pose

Sources

Primaire

Collège

Lycée

Supérieur