Recherche dichotomique : fiche de révision de 1re NSI
Publié le 6 novembre 2026 · Mis à jour le 6 novembre 2026 · Signaler une erreur
L'essentiel
La recherche dichotomique cherche une valeur dans un tableau trié : on compare avec la case du milieu, puis on ne garde qu'une moitié 3.
À chaque étape, la zone de recherche est partagée en deux parties et une seule est conservée 2 ; la boucle while s'arrête quand la valeur est trouvée ou quand la zone est vide.
Le nombre de comparaisons est logarithmique en la taille du tableau 3.
Sur un tableau de petite taille, l'avantage sur la recherche séquentielle n'est pas garanti 3.
Piège principal : appliquer l'algorithme à un tableau qui n'est pas trié.
Le principe à retenir
Le mot « dichotomie » traduit une idée simple : on partage la zone de recherche en deux parts et on n'en garde qu'une 2. Tu connais déjà le parcours séquentiel, qui regarde les cases une par une. Ici, une seule comparaison permet d'écarter la moitié des candidats.
L'algorithme pas à pas
MilieuCalculer l'indice du milieu de la zone.
ComparerComparer t[milieu] avec la valeur cherchée.
ChoisirGarder la moitié gauche ou la moitié droite.
ConclureTrouvé : renvoyer l'indice. Zone vide : absent.
Les étapes d'un tour de boucle · Un tour de la boucle de recherche dichotomique.
Pourquoi ça s'arrête et pourquoi c'est juste
Le coût : un nombre de comparaisons logarithmique
Les pièges classiques
Questions flash
4 questions · correction immédiate · ton score reste sur ton appareil.
Le tableau doit être trié : c'est ce qui permet d'écarter une moitié après une comparaison avec le milieu 3. La taille paire ou le signe des entiers n'ont aucun rôle, et un tableau avec doublons peut très bien être trié.
Le premier milieu est (0+6)//2=3, et t[3] vaut 14. Choisir 31 est tentant, mais c'est la valeur cherchée, qu'on ne trouve qu'au deuxième tour (milieu 5), après avoir constaté que 14<31.
C'est faux : l'avantage de la dichotomie apparaît surtout quand la taille augmente, et il n'est pas garanti sur un tableau de petite taille 3. Croire que le logarithme gagne toujours oublie le coût de chaque tour de boucle.
On a k≤log2(1024)=10 car 1024=2103. Répondre 1024 reviendrait à raisonner comme une recherche séquentielle, qui est linéaire.
Les questions qu'on se pose
Pourquoi la dichotomie est-elle plus efficace qu'un parcours séquentiel ?
Parce qu'une comparaison écarte la moitié des candidats, alors que le parcours séquentiel n'en écarte qu'un. Le nombre de comparaisons est logarithmique 3 contre linéaire pour la recherche séquentielle 3. L'écart devient énorme quand le tableau grossit.
Comment être sûr que ma boucle while ne tourne pas indéfiniment ?
Cherche une quantité entière positive qui diminue à chaque tour : c'est un variant. Ici, c'est la taille de la zone entre gauche et droite. Vérifie que tu écris bien milieu + 1 ou milieu - 1, sinon elle peut rester identique. La boucle while est non bornée 2, donc cette vérification est indispensable.
Que renvoyer quand la valeur n'est pas dans le tableau ?
On renvoie un signal d'absence, par exemple -1 ou None, quand la zone de recherche est vide. L'important est de documenter ce choix : la fonction a deux comportements possibles, un indice ou l'absence de la valeur 2.