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

Recherche dans une table : exercices corrigés de NSI Première

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

L'essentiel

Sur une table non triée, la seule méthode est le parcours : on teste les lignes une à une, au pire toutes.
Sur une table triée sur la colonne cherchée, la dichotomie coupe la zone de recherche en deux à chaque comparaison.
Chercher la première ligne qui convient s'arrête dès la première correspondance ; chercher toutes les lignes ou un maximum impose de tout parcourir.
Pour une table de $n$ lignes, la dichotomie demande environ $\log_2 n$ comparaisons, le parcours jusqu'à $n$ .
Erreurs classiques : condition de boucle trop stricte, oubli du cas « absent », dichotomie sur une table non triée.

Comment utiliser ces exercices

Ces exercices portent sur la recherche d'une information dans une table : un ensemble de lignes qui ont les mêmes colonnes, comme celles que tu obtiens en lisant un fichier CSV. En Python, on représente en général une table par une liste de dictionnaires : chaque dictionnaire est une ligne, chaque clé est le nom d'une colonne. Python emploie le mot « liste » pour ce qui est en réalité un tableau dynamique, doté de méthodes d'accès pratiques ³.

Les exercices sont classés par difficulté croissante. Essaie chacun sur papier avant de regarder les indices, puis compare avec la correction. Une étape de correction correspond toujours à une seule action.

MéthodeDeux façons de chercher

1. Le parcours (recherche naïve). On examine les éléments du tableau l'un après l'autre ². Cette méthode fonctionne sur n'importe quelle table, triée ou non.

2. La dichotomie. Elle exige un tableau trié : en tenant compte de ce caractère trié, on peut rendre la recherche bien plus efficace ². Le principe est le suivant ² :

on détermine l'élément $m$ situé au milieu du tableau ;
si c'est la valeur recherchée, on s'arrête avec succès ;
si $m$ est plus grand que la valeur recherchée, comme le tableau est trié, il suffit de continuer à chercher dans la moitié qui précède $m$ ;
sinon, on continue dans la moitié qui suit $m$ .

À la fin, soit on obtient un entier positif ou nul correspondant à la position de la valeur recherchée, soit la valeur n'est pas présente ².

Rappel : la dichotomie en Python

ExempleVersion de référence

def dichotomie(t, v):
    debut, fin = 0, len(t) - 1
    while debut <= fin:
        m = (debut + fin) // 2
        if t[m] == v:
            return m
        elif t[m] > v:
            fin = m - 1
        else:
            debut = m + 1
    return None

À chaque tour, la zone debut..fin est au plus divisée par deux, ce qui explique le très petit nombre de comparaisons nécessaires, même sur de grandes tables. Le test du milieu est celui décrit plus haut : trouvé, trop grand, ou trop petit ².

Les exercices

Exercice 1 Compter les comparaisons d'un parcours

★☆☆Environ 5 min

Voici une table de résultats, dans l'ordre où elle est stockée.

indice	nom	note
0	Aya	15
1	Bilal	12
2	Chloé	17
3	Dan	9
4	Emma	14

On cherche la ligne de l'élève Dan par un parcours qui s'arrête dès que le nom est trouvé. Chaque test ligne["nom"] == "Dan" compte pour une comparaison.

Combien de comparaisons sont effectuées ?

Indice 1

Écris la liste des tests dans l'ordre : ligne 0, ligne 1, etc.

Indice 2

Le parcours s'arrête juste après le test qui réussit.

Voir la correction pas à pas

On teste la ligne d'indice 0 : « Aya » n'est pas « Dan » (1 comparaison).
On teste l'indice 1 : « Bilal » n'est pas « Dan » (2 comparaisons).
On teste l'indice 2 : « Chloé » n'est pas « Dan » (3 comparaisons).
On teste l'indice 3 : « Dan » correspond, le parcours s'arrête (4 comparaisons).
La position de Dan est 3, et il a fallu $3 + 1 = 4$ comparaisons.

Pour une valeur située à l'indice $i$ , un parcours qui s'arrête au premier succès fait $i + 1$ comparaisons. Si la valeur est absente, il en fait autant que la table a de lignes.

Exercice 2 Trouver la meilleure note

★☆☆Environ 6 min

Avec la même table (notes : 15, 12, 17, 9, 14), on veut la note maximale. Contrairement à la recherche d'un nom, on ne peut pas s'arrêter avant la fin.

Explique pourquoi le parcours doit aller jusqu'à la dernière ligne.
Écris une fonction maximum(table) qui renvoie la plus grande note.
Quelle valeur renvoie-t-elle ici ?

Indice 1

Garde en mémoire la meilleure note vue jusque-là.

Indice 2

Initialise cette variable avec la note de la première ligne.

Voir la correction pas à pas

Tant qu'on n'a pas vu toutes les lignes, une note plus grande peut encore apparaître : on ne peut donc pas s'arrêter avant la fin.
On initialise meilleure avec la note de la ligne 0, soit 15.
On parcourt les lignes suivantes : 12 ne change rien, 17 devient la meilleure, 9 ne change rien, 14 ne change rien.
Code : def maximum(table): puis meilleure = table[0]["note"], une boucle for ligne in table: avec if ligne["note"] > meilleure: meilleure = ligne["note"], et enfin return meilleure.
La fonction renvoie 17.

Une recherche de maximum est un parcours complet : $n$ lignes, environ $n$ comparaisons, quelle que soit la disposition des données.

Exercice 3 Compter les occurrences

★☆☆Environ 6 min

Une table recense des livraisons. Voici la colonne ville dans l'ordre de stockage :

Lyon, Paris, Lyon, Nice, Lyon, Lille

Combien de lignes ont la ville « Lyon » ?
Peut-on utiliser une dichotomie sur cette colonne telle qu'elle est donnée ? Justifie.

Indice 1

Utilise un compteur initialisé à 0.

Indice 2

Regarde si la colonne est rangée par ordre alphabétique.

Voir la correction pas à pas

On initialise un compteur à 0.
On parcourt les six villes : Lyon (compteur 1), Paris (inchangé), Lyon (compteur 2), Nice (inchangé), Lyon (compteur 3), Lille (inchangé).
Le résultat est 3.
Pour la question 2 : la colonne n'est pas triée (Lyon, Paris, Lyon...), la dichotomie n'est donc pas applicable ².

Compter ou lister toutes les correspondances impose de parcourir toute la table, même si la table est triée : on ne peut pas s'arrêter au premier succès.

Exercice 4 Dérouler une dichotomie

★★☆Environ 10 min

Soit la colonne numero, triée par ordre croissant, d'une table de dix lignes :

t = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]

On cherche la valeur 23 avec la fonction dichotomie du rappel.

Écris, pour chaque tour, les valeurs de debut, fin, m et t[m].
Quelle position la fonction renvoie-t-elle ?
Combien de comparaisons de t[m] avec 23 ont été faites ?

Indice 1

Au départ, debut = 0 et fin = 9.

Indice 2

Le milieu est (debut + fin) // 2, division entière.

Voir la correction pas à pas

Tour 1 : debut = 0, fin = 9, m = 4, t[4] = 16. Comme 16 est plus petit que 23, on garde la moitié de droite : debut = 5.
Tour 2 : debut = 5, fin = 9, m = 7, t[7] = 56. Comme 56 est plus grand que 23, on garde la moitié de gauche : fin = 6.
Tour 3 : debut = 5, fin = 6, m = 5, t[5] = 23. La valeur est trouvée, la fonction renvoie 5.
La valeur est trouvée en 3 tours, donc en 3 comparaisons ; un parcours en aurait demandé 6, puisque 23 est à l'indice 5.

La position renvoyée est 5. Chaque tour a éliminé une moitié de la zone de recherche, c'est ce qui rend la méthode rapide.

Exercice 5 Le pire cas de la dichotomie

★★☆Environ 10 min

Une table triée compte 1000 lignes. On cherche une valeur et, dans le pire cas, la zone de recherche est réduite à une moitié à chaque tour, sans jamais tomber sur la valeur avant la fin.

Écris la taille maximale de la zone avant chaque comparaison, en partant de 1000 et en arrondissant vers le bas à chaque division par 2.
En déduire le nombre maximal de comparaisons.
Vérifie avec la formule $\lfloor \log_2 n \rfloor + 1$ .

Indice 1

Les tailles s'écrivent 1000, 500, 250, ...

Indice 2

Arrête-toi quand la taille atteint 1 : il reste alors une dernière comparaison.

Voir la correction pas à pas

Tailles successives de la zone : 1000, 500, 250, 125, 62, 31, 15, 7, 3, 1.
Chaque taille correspond à une comparaison : il y a 10 valeurs dans la liste, donc 10 comparaisons au maximum.
Formule : $\log_2 1000 \approx 9{,}97$ , donc $\lfloor \log_2 1000 \rfloor = 9$ et $9 + 1 = 10$ .
Les deux méthodes donnent le même résultat : 10.

Chercher dans 1000 lignes triées demande au plus 10 comparaisons, contre 1000 pour un parcours dans le pire cas.

Exercice 6 Parcours ou dichotomie : mesurer le gain

★★☆Environ 8 min

Une table triée compte 5000 lignes. Une valeur absente est recherchée.

Combien de comparaisons fait un parcours complet ?
Combien en fait au plus une dichotomie ?
Quelle économie, en nombre de comparaisons, la dichotomie réalise-t-elle dans ce pire cas ?

Indice 1

Pour une valeur absente, le parcours examine toutes les lignes.

Indice 2

Utilise la formule $\lfloor \log_2 n \rfloor + 1$ ; on a $2^{12} = 4096$ et $2^{13} = 8192$ .

Voir la correction pas à pas

Un parcours complet examine les 5000 lignes : 5000 comparaisons.
Comme $4096 \le 5000 < 8192$ , on a $\lfloor \log_2 5000 \rfloor = 12$ .
La dichotomie fait donc au plus $12 + 1 = 13$ comparaisons.
Économie : $5000 - 13 = 4987$ comparaisons.

Le gain croît avec la taille de la table : c'est pourquoi on trie une table que l'on doit interroger souvent, même si le tri a lui-même un coût.

Exercice 7 Écrire une recherche dans une table de dictionnaires

★★☆Environ 12 min

On dispose d'une table eleves, liste de dictionnaires de clés "nom", "classe" et "note".

Écris une fonction rechercher(table, champ, valeur) qui renvoie la première ligne dont la colonne champ vaut valeur, ou None s'il n'y en a pas.
Écris rechercher_tout(table, champ, valeur) qui renvoie la liste de toutes les lignes correspondantes.
Explique en une phrase pourquoi la première fonction peut s'arrêter plus tôt que la seconde.

Indice 1

Une instruction return à l'intérieur de la boucle arrête la fonction.

Indice 2

Pour la seconde fonction, construis une liste de résultats que tu complètes avec append.

Voir la correction pas à pas

Première fonction : on parcourt for ligne in table:.
Dans la boucle : if ligne[champ] == valeur: return ligne, qui sort dès le premier succès.
Après la boucle, on écrit return None, qui traite le cas où la valeur est absente.
Seconde fonction : on crée res = [], on parcourt toute la table, on fait res.append(ligne) à chaque correspondance, puis return res.
La première s'arrête au premier succès ; la seconde doit voir toutes les lignes, car une autre correspondance peut se trouver plus loin.

Code attendu : def rechercher(table, champ, valeur): suivi de for ligne in table:, if ligne[champ] == valeur: return ligne, puis return None à la fin, hors de la boucle. Un return None placé dans la boucle est une erreur classique : la fonction s'arrêterait après la première ligne.

Exercice 8 Corriger une dichotomie fautive

★★★Environ 12 min

Un élève propose cette fonction :

def dicho(t, v):
    d, f = 0, len(t) - 1
    while d < f:
        m = (d + f) // 2
        if t[m] == v:
            return m
        elif t[m] > v:
            f = m - 1
        else:
            d = m + 1
    return None

Teste-la à la main avec t = [3, 7, 10] et v = 10.
Teste-la avec t = [4] et v = 4.
Identifie l'erreur et propose la correction.
Que se passerait-il si on l'appelait sur [10, 3, 7] (non trié) avec v = 3 ?

Indice 1

Regarde ce qui se passe quand d et f deviennent égaux.

Indice 2

Dans le cas d == f, il reste encore un élément à examiner.

Voir la correction pas à pas

Avec [3, 7, 10] et 10 : d = 0, f = 2, m = 1, t[1] = 7 < 10, donc d = 2. Maintenant d < f est faux : la boucle s'arrête et la fonction renvoie None, alors que 10 est à l'indice 2.
Avec [4] et 4 : d = 0, f = 0, la condition 0 < 0 est fausse dès le début, la fonction renvoie None alors que 4 est présent.
L'erreur vient de la condition : quand d == f, la zone contient encore un élément qui n'a pas été comparé. Il faut écrire while d <= f:.
Avec la correction, les deux tests renvoient bien 2 et 0.
Sur [10, 3, 7] avec 3 : m = 1, t[1] = 3 est trouvé par chance. Mais avec v = 10, t[1] = 3 < 10 conduit à chercher à droite et on rate 10 : sans tri préalable, le résultat n'est pas fiable ².

Deux conditions garantissent une dichotomie correcte : while debut <= fin pour examiner la dernière case, et une table triée sur la colonne cherchée. Teste toujours avec une table d'un seul élément, deux éléments, et une valeur absente.

Les questions qu'on se pose

Pourquoi ne pas toujours utiliser la dichotomie, puisqu'elle est plus rapide ?

Parce qu'elle n'est valable que si la table est triée sur la colonne cherchée ². Sur une table non triée, il faut soit la trier d'abord, soit se contenter d'un parcours. Pour une recherche unique dans une petite table, le parcours est tout à fait raisonnable ; pour des recherches nombreuses dans une grande table, trier une fois puis chercher par dichotomie est avantageux.

Que renvoyer quand la valeur n'est pas dans la table ?

À toi de choisir une convention et de la tenir. Les fonctions de ces exercices renvoient None quand rien ne correspond, ce qui est facile à tester avec if resultat is None. Une position de succès, elle, est un entier positif ou nul ², c'est pourquoi on évite de renvoyer 0 pour signaler un échec : 0 est une position valide.

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.

Signaler une erreur sur cette page

Recherche dans une table : exercices corrigés de NSI Première

L'essentiel

Comment utiliser ces exercices

Rappel : la dichotomie en Python

Les exercices

Exercice 1 Compter les comparaisons d'un parcours

Exercice 2 Trouver la meilleure note

Exercice 3 Compter les occurrences

Exercice 4 Dérouler une dichotomie

Exercice 5 Le pire cas de la dichotomie

Exercice 6 Parcours ou dichotomie : mesurer le gain

Exercice 7 Écrire une recherche dans une table de dictionnaires

Exercice 8 Corriger une dichotomie fautive

Les questions qu'on se pose

Sources

Primaire

Collège

Lycée

Supérieur