Algorithmes de seuil et de dichotomie : fiche de Terminale
Publié le 7 novembre 2026 · Mis à jour le 7 novembre 2026 · Signaler une erreur
L'essentiel
Un algorithme de seuil répète un calcul avec une boucle while jusqu'à ce qu'une condition soit remplie, puis renvoie le rang trouvé.
La dichotomie coupe à chaque étape l'intervalle de recherche en deux et garde une seule moitié.
Dans les deux cas la boucle est non bornée : on ne sait pas à l'avance combien de tours seront nécessaires.
Pour éviter une boucle infinie, la condition d'arrêt doit finir par devenir fausse à coup sûr.
Après k coupures, la longueur de l'intervalle initial est divisée par 2k.
Seuil : répéter jusqu'à dépasser une valeur
Dichotomie : couper en deux à chaque étape
Dichotomie dans un tableau trié
La recherche dichotomique traite efficacement des données rangées dans un tableau de façon ordonnée 2. On compare la valeur cherchée à l'élément du milieu, puis on ne garde que la moitié qui peut la contenir. Si l'intervalle devient vide, la valeur n'est pas présente 2.
Choisir son algorithme
Questions flash
4 questions · correction immédiate · ton score reste sur ton appareil.
On continue tant que le seuil n'est pas atteint, donc tant que u≥10. while u < 10 est la tentation fréquente, mais elle ne démarre jamais puisque u0=100. for n in range(10) fixe 10 tours à l'avance, alors que le nombre de tours est inconnu.
Après 7 coupures, la longueur est 271=1281=0,0078125≈0,008 au millième. Se tromper en calculant 7×21 revient à confondre une puissance de 2 avec un produit.
C'est faux : le choix de la moitié à garder repose sur la comparaison avec l'élément du milieu, ce qui n'a de sens que si la liste est ordonnée. Dans une liste en désordre, la valeur peut se trouver dans la moitié écartée.
Comme f(a)<0 et f(m)>0, la solution est entre a et m : on garde [a;m] en posant b = m. Remplacer a par m ferait garder la moitié où f garde le même signe aux deux bords, donc sans solution assurée.
Les questions qu'on se pose
Comment être sûr que ma boucle while s'arrête ?
Repère la grandeur qui change à chaque tour : le terme de la suite qui décroît vers le seuil, ou la longueur de l'intervalle qui est divisée par 2. Vérifie que cette évolution finit par rendre la condition fausse. Une boucle while est non bornée, donc cette vérification te revient 2.
Quelle différence entre une boucle for et une boucle while ?
La boucle for répète un nombre de fois connu à l'avance. La boucle while, dite non bornée, s'utilise quand ce nombre est inconnu, comme pour un seuil ou une dichotomie 2.
Pourquoi la dichotomie est-elle plus efficace qu'un parcours de la liste ?
Un parcours complet double de durée quand la liste double de taille 2. La dichotomie élimine la moitié des candidats à chaque étape : doubler la taille de la liste ajoute seulement un tour de boucle.