Numérique et sciences informatiques (spécialité) · Première
Recherche dichotomique : quiz de NSI en Première
Publié le 7 novembre 2026 · Mis à jour le 7 novembre 2026 · Signaler une erreur
L'essentiel
- La recherche dichotomique cherche un élément dans un tableau trié en le comparant à la valeur du milieu, puis en poursuivant dans la moitié pertinente 3.
- À chaque étape, l'intervalle de recherche est coupé en deux : la taille est divisée par 2 à chaque itération 23.
- Le nombre de comparaisons est logarithmique en la taille du tableau, alors que la recherche séquentielle est linéaire 3.
- Sur un petit tableau, la dichotomie n'est pas forcément plus rapide que le parcours séquentiel 3.
Avant de commencer
Ce quiz porte sur la recherche dichotomique : son principe, la condition pour l'utiliser, le déroulement à la main sur un exemple, la boucle while qui la programme, et son coût. Tu y retrouveras aussi quelques comparaisons avec d'autres façons de chercher une valeur. Tu as déjà vu le parcours séquentiel d'un tableau et les tris par insertion et par sélection : c'est exactement ce qu'il faut pour aborder ces questions.
Quiz
15 questions · correction immédiate · ton score reste sur ton appareil.
-
La recherche dichotomique sert à trouver la position d'un élément dans un tableau trié 3. C'est le tri qui permet, après comparaison avec le milieu, d'éliminer toute une moitié. Les autres propositions sont des idées fausses fréquentes : la parité de la taille ne change rien (on arrondit simplement le calcul du milieu), et le signe ou l'unicité des valeurs ne sont pas nécessaires au principe.
-
On compare l'élément cherché à la valeur de la case du milieu 3. Comparer au premier élément, c'est le début d'un parcours séquentiel, pas d'une dichotomie. Et le tri n'est pas une étape de l'algorithme : il doit être fait avant.
-
C'est faux. Si le tableau n'est pas trié, savoir que
tab[milieu] < xne dit rien sur la position dex: il peut très bien se trouver à gauche. On risquerait d'écarter la moitié qui contient la valeur. À l'inverse, la recherche séquentielle n'a pas besoin d'un tableau trié 3. -
La taille est divisée par 2 à chaque itération, donc après itérations elle vaut 3. Ici : . Si tu as trouvé 500, tu as calculé une seule division ; si tu as trouvé 333, tu as divisé par 3 au lieu de diviser par .
-
Tour 1 :
debut = 0,fin = 9,milieu = 4,tab[4] = 16 < 23doncdebut = 5. Tour 2 :milieu = (5 + 9) // 2 = 7,tab[7] = 56 > 23doncfin = 6. Tour 3 :milieu = (5 + 6) // 2 = 5,tab[5] = 23, la fonction renvoie 5. L'erreur tentante est de répondre 6 en comptant à partir de 1 : en Python, les indices commencent à 0. -
Si la valeur du milieu est plus petite que
x, comme le tableau est trié,xne peut se trouver que plus à droite : on repart demilieu + 1.fin = milieu - 1fait l'inverse et éliminerait la bonne moitié. Écriredebut = milieuest un piège : la case du milieu a déjà été testée, et dans certains cas la zone ne rétrécit plus (par exemple avecdebut = 5,fin = 6, on retrouvemilieu = 5indéfiniment), ce qui donne une boucle infinie. -
La fonction contient bien une boucle
while, non bornée 2. Elle s'arrête soit parce quetab[milieu] == x, soit parce quedebut > fin, ce qui signifie que la zone est vide et que la valeur est absente. Commedebutaugmente oufindiminue à chaque tour, la zone rétrécit, ce qui garantit l'arrêt. La proposition sur la boucleforest fausse : le nombre exact de tours n'est pas connu d'avance, puisqu'il dépend de la valeur cherchée, qui peut être trouvée dès le premier tour. -
À chaque tour la zone se réduit ; au bout d'un moment
debut > finet la condition duwhiledevient fausse. La fonction renvoie alors une valeur spéciale qui indique que la valeur recherchée n'est pas présente 2 ; dans notre code, c'estNone. La boucle infinie n'arrive qu'avec une mise à jour erronée des bornes, pas avec le code correct. -
C'est faux. La recherche séquentielle consiste à examiner les éléments les uns après les autres, en temps linéaire, et elle ne nécessite pas de structure triée. Elle peut même s'utiliser sur une liste chaînée 3. C'est justement ce qui fait sa polyvalence, au prix d'un coût plus élevé sur les grands tableaux.
-
L'avantage de la dichotomie est de nature asymptotique : il apparaît quand la taille du tableau grandit, et rien ne l'assure sur un tableau minuscule 3. Dire qu'elle est « toujours » plus rapide est l'erreur classique. Dire que la séquentielle gagne « toujours » est faux aussi, puisque sur de grands tableaux l'écart devient énorme.
-
C'est vrai : la recherche dichotomique est présentée comme un cas particulier important de la méthode diviser pour régner 4. L'idée commune est de ramener un problème à un problème plus petit, ici une moitié de tableau. Attention à ne pas la confondre avec la dichotomie en mathématiques pour trouver un zéro de fonction, qui utilise la même idée de coupure en deux mais dans un autre contexte 4.
-
La taille finale vaut et elle est au moins égale à 1. On obtient , puis, en composant par le logarithme (fonction croissante) et en divisant par , 3. Tester chaque élément une fois donnerait un nombre de tests proportionnel à , comme en séquentiel. Et le logarithme est croissant, pas décroissant : c'est ce qui permet de conserver l'inégalité.
-
Au premier tour,
debut = 0etfin = 6, doncmilieu = (0 + 6) // 2 = 3. On littab[3] = 7, qui est plus grand que 5 : on poursuit dans la moitié gauche avecfin = 2. Au tour suivant,milieu = (0 + 2) // 2 = 1, puisdebut = 2et enfinmilieu = 2, où l'on trouve 5. -
Si la valeur du milieu est plus grande que
x, comme le tableau est trié,xne peut se trouver que plus à gauche. On repart donc avecfin = milieu - 1, car la case du milieu a déjà été testée. Les deux propositions sans+ 1ou- 1risquent de laisser la zone inchangée et de provoquer une boucle infinie.
Les questions qu'on se pose
Comment vérifier à la main que j'ai bien déroulé l'algorithme ?
Fais un tableau avec une ligne par tour et les colonnes debut, fin, milieu, tab[milieu], puis la décision prise. Vérifie à chaque ligne que la zone est plus petite qu'à la ligne précédente : si elle ne rétrécit pas, c'est qu'une borne est mal mise à jour. L'algorithme coupe l'intervalle en deux à chaque étape 2, donc le nombre de lignes reste très petit.
Pourquoi dit-on que la dichotomie est « plus rapide » si elle ne l'est pas toujours ?
Parce qu'on compare des comportements quand la taille du tableau devient grande. Le nombre de comparaisons de la dichotomie est logarithmique, celui de la recherche séquentielle est linéaire 3. Sur un tout petit tableau, la différence est faible, et la dichotomie n'est pas forcément plus rapide 3. Pour tes évaluations, retiens surtout la condition d'usage : un tableau trié.
Que faire si le tableau n'est pas trié ?
Deux options. Tu peux utiliser la recherche séquentielle, qui ne demande pas de tableau trié 3. Ou tu peux d'abord trier le tableau (par insertion ou par sélection, comme tu l'as vu), puis utiliser la dichotomie. Cela n'est intéressant que si tu fais de nombreuses recherches, car le tri a lui-même un coût.
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.