Numérique et sciences informatiques (spécialité) · Première
Recherche dans une table : quiz de 1re NSI
Publié le 6 novembre 2026 · Mis à jour le 6 novembre 2026 · Signaler une erreur
L'essentiel
- Une recherche naïve parcourt la table élément par élément ; elle fonctionne sur n'importe quelle table, triée ou non.2
- La recherche dichotomique exige une table triée : on regarde l'élément du milieu, puis on garde la moitié qui peut encore contenir la valeur.2
- Si l'élément du milieu est la valeur cherchée, on s'arrête avec succès ; sinon, on continue dans la moitié utile.2
- En cas de succès, on renvoie une position ; en cas d'absence, la fonction doit le signaler autrement, par exemple par une valeur qui n'est pas une position.2
Avant de commencer
Ce quiz couvre la recherche d'une valeur dans une table : la recherche par parcours, puis, pour une table triée, la recherche par dichotomie. Tu peux le faire après avoir revu l'indexation d'une table et le format CSV, et avant d'aborder le tri et la fusion de tables.
Pour chaque question, essaie de répondre sans relire le rappel, puis lis l'explication, y compris quand ta réponse est juste : elle précise souvent pourquoi l'erreur tentante est fausse. Les tables des questions sont indexées à partir de 0, comme en Python.
Quiz
14 questions · correction immédiate · ton score reste sur ton appareil.
-
La dichotomie s'appuie sur le caractère trié de la table : c'est lui qui permet d'écarter une moitié après une comparaison.2 Le type des valeurs n'est pas en cause : des chaînes triées conviennent aussi. Le nombre d'éléments pair n'a aucune importance, on choisit simplement un élément « du milieu ». Les doublons ne bloquent pas la méthode : on obtient alors l'une des positions de la valeur.2
-
Vrai. La recherche naïve consiste à parcourir la table et à comparer chaque élément à la valeur cherchée.2 Elle n'utilise aucune propriété d'ordre, donc elle fonctionne sur n'importe quelle table. La condition « table triée » concerne seulement la dichotomie.
-
La table étant triée, tout ce qui est après est au moins aussi grand que , donc strictement plus grand que la valeur cherchée : il suffit de chercher avant .2 Chercher après est l'erreur typique de qui inverse le sens de l'inégalité. Conclure à l'absence serait prématuré : la valeur peut très bien se trouver avant .
-
Le milieu des indices 0 à 6 est l'indice 3, qui contient 11. Comme , on garde les indices 4 à 6. Leur milieu est l'indice 5, qui contient 17 : c'est la valeur cherchée, on s'arrête et on renvoie 5.2 Répondre 17 confond la valeur avec sa position ; répondre 6 vient d'un décalage d'une unité, l'indexation commençant à 0.
-
On consulte d'abord le milieu des 7 éléments. Il en reste au plus 3 d'un côté : on consulte leur milieu. Il en reste au plus 1 : on le consulte. Cela fait 3 consultations au plus. Une recherche par parcours en aurait demandé jusqu'à 7. Répondre 7 revient à oublier qu'on écarte une moitié à chaque étape ; répondre 4 vient d'un arrondi mal fait en divisant 7 par 2 plusieurs fois.
-
Si le milieu est la valeur cherchée, on s'arrête avec un succès.2 Il n'y a plus rien à chercher. Continuer dans une moitié n'aurait de sens que si le milieu était différent de la valeur.
-
La dichotomie exploite le tri pour écarter une partie de la table après chaque comparaison avec le milieu.2 La recherche naïve, elle, n'exige aucun tri : la deuxième proposition est fausse. Quant à la dernière, une recherche naïve compare bien chaque élément parcouru à la valeur cherchée, donc elle est fausse aussi.
-
Dans une table de données, on compare la valeur du champ sur lequel la table est triée. Ici le tri porte sur les noms : c'est donc
"nom"qu'il faut comparer. Comparer la note à "Martin" n'a aucun sens : ce n'est pas le même type de donnée, et de toute façon la table n'est pas triée selon ce champ. Comparer un dictionnaire entier à une chaîne ne permet pas non plus de savoir de quel côté continuer. -
En cas de succès, on renvoie un entier positif ou nul qui correspond à une position de la valeur dans la table.2 Renvoyer la valeur elle-même n'apprendrait rien, puisqu'on la connaît déjà. Le nombre de comparaisons ou la taille de la table sont des informations sur le déroulement de l'algorithme, pas sur le résultat de la recherche.
-
En cas de répétition, la recherche renvoie l'une des positions de la valeur.2 Avec la dichotomie, on s'arrête dès qu'on tombe sur le milieu égal à la valeur, sans garantie que ce soit la première occurrence. Si l'on veut absolument la première, il faut prévoir un traitement supplémentaire.
-
Savoir qu'un élément n'est pas la valeur recherchée n'apprend rien sur les autres valeurs de la table.2 C'est exactement ce qui change quand la table est triée : une comparaison avec le milieu renseigne alors sur toute une moitié. Supposer que les autres sont plus grands ou plus petits reviendrait à croire, à tort, que la table est ordonnée.
-
Faux. Un entier positif ou nul est réservé au cas où la valeur est trouvée : c'est une position.2 En cas d'absence, la fonction doit renvoyer autre chose, par exemple
Noneou-1, pour que l'appelant ne confonde pas échec et position valide. Renvoyer 0 pour « absent » serait une faute, car 0 est la position du premier élément. -
Python emploie le terme « liste » pour ce qui est en réalité un tableau dynamique avec des méthodes d'accès typiques.3 C'est pour cela qu'on accède à un élément par son indice, ce qui est indispensable à la dichotomie, qui doit atteindre directement le milieu. Un arbre binaire de recherche est une autre structure, étudiée à part, qui offre aussi une recherche efficace.3
Les questions qu'on se pose
Pourquoi ne pas toujours utiliser la dichotomie, puisqu'elle écarte une partie de la table à chaque étape ?
Parce qu'elle n'est valable que sur une table triée.2 Sur une table non triée, comparer le milieu ne dit rien sur le reste, donc on ne peut écarter aucune moitié. Il faut alors une recherche par parcours. Trier d'abord une table pour une seule recherche coûte en général plus cher que la parcourir ; la dichotomie devient intéressante quand on fait de nombreuses recherches dans une table déjà triée.
Comment savoir quand arrêter la dichotomie si la valeur est absente ?
Tu arrêtes quand la partie de la table qui reste à explorer est vide : à ce stade, la valeur n'est pas présente.2 Dans le code, cela correspond à une condition de boucle du type « début ≤ fin » qui devient fausse. La fonction renvoie alors une valeur qui n'est pas une position, comme None, pour signaler l'échec.
Sources
Programme visé : Programme NSI Première — Traitement de données en tables · Éduscol - Ministère de l'Éducation nationale
- Programme NSI Première — Traitement de données en tables, Éduscol - Ministère de l'Éducation nationale. Consulté le 6 novembre 2026.
- Recherche dichotomique — Ressource d'accompagnement NSI Première, Éduscol. Consulté le 6 novembre 2026.
- Structures de données — Document de ressource NSI, Éduscol. Consulté le 6 novembre 2026.
- Tableau périodique des éléments, Wikipédia. Consulté le 6 novembre 2026.
- Tad l'explorateur et la table d'émeraude, 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.