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

La recherche dans une table : cours de NSI en Première

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

L'essentiel

Chercher dans une table, c'est parcourir ses lignes pour retrouver une valeur ou un enregistrement : on renvoie sa position, ou une valeur convenue (ici None) si elle est absente.
La recherche séquentielle fonctionne sur n'importe quelle table, mais elle peut examiner toutes les lignes : son coût grandit avec la taille de la table.
La recherche dichotomique exige une table triée : on compare au milieu, on garde la moitié utile, on recommence.
Pour la dichotomie, la boucle while debut <= fin avec m = (debut + fin) // 2 et les mises à jour fin = m - 1 ou debut = m + 1 évitent les boucles infinies.
Un arbre binaire de recherche applique la même idée de tri : à chaque nœud, on choisit le fils gauche ou le fils droit.

Chercher dans une table : de quoi parle-t-on ?

Tu as déjà manipulé des tables : un fichier CSV que l'on charge en Python devient une liste de lignes, et chaque ligne est souvent un dictionnaire dont les clés sont les descripteurs (« nom », « note », « classe »). Une question revient sans cesse avec ces données : la valeur que je veux est-elle dans la table, et si oui, où ?

C'est ce problème qu'on appelle la recherche. Dans ce cours, on étudie deux méthodes pour le résoudre sur un tableau de valeurs ou sur une table de lignes, puis on compare leur efficacité. Tu en auras besoin ensuite pour comprendre le tri d'une table et la fusion de tables, car ces opérations s'appuient sur des comparaisons entre valeurs.

La recherche séquentielle (parcours complet)

La première façon de chercher une valeur dans un tableau est la plus naïve : on parcourt le tableau case après case ². Elle ne demande aucune hypothèse sur l'ordre des valeurs, ce qui en fait la méthode universelle.

Voici la fonction correspondante :

def recherche_sequentielle(t, v):
    """Renvoie un indice de v dans t, ou None si v est absente."""
    for i in range(len(t)):
        if t[i] == v:
            return i
    return None

Le return i à l'intérieur de la boucle interrompt immédiatement la fonction : on n'examine pas le reste du tableau. Le return None n'est atteint que si la boucle va jusqu'au bout sans rien trouver.

ExempleUn exemple pas à pas

On prend t = [12, 7, 30, 7, 19] et on cherche v = 7.

Tour	`i`	`t[i]`	Égal à 7 ?
1	0	12	non
2	1	7	oui, on renvoie 1

Le 7 apparaît aussi à l'indice 3, mais la fonction s'arrête dès la première occurrence : elle renvoie 1. Si on cherche v = 5, les cinq cases sont examinées sans succès et la fonction renvoie None.

Attention, erreur fréquenteNe pas mettre le `return None` dans la boucle

Une erreur très fréquente consiste à écrire :

for i in range(len(t)):
    if t[i] == v:
        return i
    else:
        return None

Cette version abandonne dès la première case : si t[0] n'est pas la valeur cherchée, elle renvoie None sans avoir regardé les autres cases. Un test négatif sur une seule case ne dit rien des autres valeurs du tableau ². Le return None se place après la boucle.

Rechercher dans une table de lignes

Une vraie table contient des lignes avec plusieurs champs. On ne compare plus la ligne entière à la valeur : on compare un champ (la clé de recherche) à la valeur cherchée. La structure de l'algorithme reste identique.

ExempleRetrouver un élève par son nom

On dispose de la table :

eleves = [
    {"nom": "Alice", "note": 14},
    {"nom": "Bilal", "note": 9},
    {"nom": "Camille", "note": 17},
    {"nom": "Dylan", "note": 12},
]

def chercher_eleve(table, nom):
    for i in range(len(table)):
        if table[i]["nom"] == nom:
            return i
    return None

L'appel chercher_eleve(eleves, "Camille") renvoie 2. L'appel chercher_eleve(eleves, "Emma") renvoie None. Pour obtenir la note, on écrit ensuite eleves[2]["note"], soit 17.

MéthodeTrois variantes utiles

Selon la question, on adapte le parcours :

Renvoyer la ligne plutôt que l'indice : return table[i].
Renvoyer tous les indices qui conviennent : on remplit une liste au fil du parcours, sans jamais s'arrêter avant la fin.
Chercher un extremum (la meilleure note par exemple) : on garde en mémoire la meilleure valeur vue jusque-là et on la met à jour.

def indices_note_superieure(table, seuil):
    resultat = []
    for i in range(len(table)):
        if table[i]["note"] >= seuil:
            resultat.append(i)
    return resultat

Avec la table précédente et seuil = 12, on obtient [0, 2, 3].

La recherche dichotomique dans un tableau trié

Un test raté sur une case n'apprend rien sur les autres cases tant que le tableau est en désordre ². Mais si le tableau est trié, la situation change : une seule comparaison peut éliminer toute une moitié du tableau. En exploitant le caractère trié, on améliore nettement l'efficacité de la recherche ². C'est la recherche dichotomique (du grec « couper en deux »).

MilieuCalculer m = (debut + fin) // 2
ComparerComparer t[m] à la valeur cherchée
GarderGarder la moitié gauche ou droite
RecommencerMettre à jour debut ou fin
ArrêterSuccès ou zone vide : debut > fin

Les étapes de la dichotomie · Le déroulé d'une recherche dichotomique.

ExempleUn déroulé complet

On cherche v = 27 dans t = [3, 8, 12, 15, 21, 27, 34, 40, 52] (indices de 0 à 8).

Tour	`debut`	`fin`	`m`	`t[m]`	Décision
1	0	8	4	21	$21 < 27$ : on garde la droite, `debut = 5`
2	5	8	6	34	$34 > 27$ : on garde la gauche, `fin = 5`
3	5	5	5	27	trouvé : on renvoie 5

Trois comparaisons ont suffi, alors qu'un parcours depuis le début en aurait demandé six.

Écrire la dichotomie en Python

On représente la zone de recherche par deux indices : debut (inclus) et fin (inclus). Au départ, la zone couvre tout le tableau. À chaque tour, on la réduit.

MéthodeLe code de référence

def dichotomie(t, v):
    """Renvoie un indice de v dans le tableau trié t, ou None."""
    debut = 0
    fin = 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

Le // est la division entière : pour une zone de 4 cases (indices 2 à 5), $m = (2 + 5) // 2 = 3$ .

Lis bien les deux mises à jour. On ne garde jamais m dans la nouvelle zone, puisqu'on vient de constater qu'il n'est pas la bonne valeur : la zone de gauche se termine à m - 1, celle de droite commence à m + 1.

Démonstration · Pourquoi la boucle se termine toujours

La quantité $\text{fin} - \text{debut} + 1$ est le nombre de cases de la zone de recherche.

Si $t[m] > v$ , la nouvelle zone va de debut à m - 1. Comme $m \geq \text{debut}$ , elle contient au plus $m - \text{debut}$ cases, soit strictement moins que la zone précédente (qui contenait au moins $m - \text{debut} + 1$ cases).
Si $t[m] < v$ , la nouvelle zone va de m + 1 à fin. Comme $m \leq \text{fin}$ , elle contient au plus $\text{fin} - m$ cases, soit strictement moins que l'ancienne zone (qui en contenait au moins $\text{fin} - m + 1$ ).

Le nombre de cases est donc un entier positif ou nul qui diminue strictement à chaque tour. Il ne peut pas diminuer indéfiniment : un moment, la zone est vide (debut > fin) et la boucle s'arrête. C'est un variant de boucle.

Comparer le coût des deux méthodes

Pour juger un algorithme de recherche, on compte le nombre de comparaisons entre la valeur cherchée et une case du tableau. Ce nombre dépend de la taille $n$ du tableau et de la position de la valeur.

Taille de la table	Séquentielle	Dichotomie (tours au plus)
15	15	4
1 000	1 000	10
1 000 000	1 000 000	20

Ouverture : l'arbre binaire de recherche

Un tableau trié permet de chercher vite, mais y insérer de nouveaux éléments en conservant l'ordre coûte cher. Une autre structure de données prend en charge à la fois l'ajout d'une valeur et le test de sa présence ³ : l'arbre binaire de recherche.

Bilan et erreurs fréquentes

Exercices corrigés

Exercice 1 Dérouler une dichotomie

★☆☆Environ 8 min

On considère le tableau trié t = [3, 8, 12, 15, 21, 27, 34, 40, 52] (indices de 0 à 8). On exécute dichotomie(t, 40) avec la fonction du cours.

Écris le tableau des valeurs de debut, fin, m et t[m] à chaque tour.
Quelle valeur la fonction renvoie-t-elle ?

Indice 1

Pour le premier tour, m = (0 + 8) // 2.

Indice 2

Si t[m] est plus petit que la valeur cherchée, on poursuit à droite avec debut = m + 1.

Voir la correction pas à pas

Tour 1 : debut = 0, fin = 8, donc m = 4 et t[4] = 21. Comme 21 < 40, on garde la droite : debut = 5.
Tour 2 : debut = 5, fin = 8, donc m = (5 + 8) // 2 = 6 et t[6] = 34. Comme 34 < 40, debut = 7.
Tour 3 : debut = 7, fin = 8, donc m = (7 + 8) // 2 = 7 et t[7] = 40. La valeur cherchée est trouvée.
La fonction renvoie l'indice 7, après trois comparaisons.

La fonction renvoie 7 en trois tours. Remarque que l'on renvoie l'indice m, pas la valeur 40.

Exercice 2 Rechercher des élèves dans une table

★★☆Environ 15 min

Une table d'élèves est représentée par une liste de dictionnaires :

eleves = [
    {"nom": "Alice", "note": 14},
    {"nom": "Bilal", "note": 9},
    {"nom": "Camille", "note": 17},
    {"nom": "Dylan", "note": 12},
]

Écris une fonction note_de(table, nom) qui renvoie la note de l'élève nommé, ou None s'il est absent.
Écris une fonction meilleure_note(table) qui renvoie la plus haute note de la table (on suppose la table non vide), sans utiliser max.
Pour quel champ la dichotomie est-elle utilisable avec cette table telle qu'elle est : "nom" ou "note" ? Justifie.

Indice 1

Pour la question 2, initialise la meilleure note avec celle de la première ligne.

Indice 2

Pour la question 3, regarde si les valeurs de chaque champ sont rangées dans l'ordre croissant.

Voir la correction pas à pas

Question 1 : on parcourt les lignes et on renvoie la note dès que le nom correspond.

def note_de(table, nom):
    for ligne in table:
        if ligne["nom"] == nom:
            return ligne["note"]
    return None

Le return None se place après la boucle, pour ne répondre « absent » qu'après avoir examiné toutes les lignes.

Question 2 : on garde en mémoire la meilleure note vue, qu'on met à jour quand une note est plus grande.

def meilleure_note(table):
    meilleure = table[0]["note"]
    for ligne in table:
        if ligne["note"] > meilleure:
            meilleure = ligne["note"]
    return meilleure

Sur la table donnée, elle renvoie 17.

Question 3 : les noms Alice, Bilal, Camille, Dylan sont dans l'ordre alphabétique, donc la table est triée selon "nom" et la dichotomie y fonctionne. En revanche, les notes 14, 9, 17, 12 ne sont pas dans l'ordre : la dichotomie ne fonctionnerait pas sur "note".

La dichotomie est possible sur "nom" (table triée selon ce champ), pas sur "note". Le critère est toujours « trié selon le champ cherché ».

Exercice 3 Borner le nombre de comparaisons dans un ABR

★★★Environ 10 min

Un arbre binaire de recherche a pour hauteur $h = 6$ . On y cherche une valeur absente de l'arbre.

Quel est le nombre maximal de comparaisons effectuées ?
Un arbre de hauteur 6 peut-il contenir 1 000 valeurs ? Justifie en comptant le nombre maximal de nœuds à chaque niveau (la racine est au niveau 0).

Indice 1

Applique la borne $h + 1$ du cours.

Indice 2

À chaque niveau, un nœud a au plus deux fils : le nombre maximal de nœuds double d'un niveau au suivant.

Voir la correction pas à pas

Question 1 : le nombre de comparaisons est borné par $h + 1$ . Avec $h = 6$ , on obtient $6 + 1 = 7$ comparaisons au plus.
Question 2 : la racine est au niveau 0 et chaque niveau peut contenir au plus deux fois plus de nœuds que le précédent : 1, 2, 4, 8, 16, 32, 64 nœuds pour les niveaux 0 à 6.
On additionne : $1 + 2 + 4 + 8 + 16 + 32 + 64 = 127$ nœuds au maximum.
Comme $127 < 1000$ , un arbre de hauteur 6 ne peut pas contenir 1 000 valeurs : il faudrait une hauteur plus grande, donc davantage de comparaisons possibles.

La borne est 7 comparaisons. Un arbre de hauteur 6 contient au plus 127 nœuds, donc pour ranger 1 000 valeurs il faut un arbre plus haut.

Les questions qu'on se pose

Pourquoi ne pas toujours utiliser la dichotomie, puisqu'elle va plus vite ?

Parce qu'elle exige un tableau trié selon le champ cherché. Sur une table en désordre, la méthode peut rater une valeur présente. Si tu ne fais qu'une recherche dans une table non triée, le parcours séquentiel est plus simple et plus sûr, car trier coûte lui-même du travail. La dichotomie devient intéressante quand la table est déjà triée ou qu'on y fait de nombreuses recherches.

Que renvoyer quand la valeur n'est pas trouvée ?

Il faut une valeur qui ne peut pas être confondue avec un indice valide. Un résultat positif ou nul signale une position trouvée ² ; on utilise donc None (ou parfois -1) pour l'échec. L'important est de choisir une convention, de la documenter dans la fonction et de la tester côté appelant avec is not None, car l'indice 0 est vu comme faux par un simple if.

Que se passe-t-il si la valeur apparaît plusieurs fois ?

Dans le problème « trouver une position », n'importe quelle position de la valeur est une réponse correcte ². La recherche séquentielle renvoie la première occurrence, car elle parcourt de gauche à droite. La dichotomie renvoie celle sur laquelle elle tombe en premier, qui peut être une autre. Si l'énoncé exige la première ou la dernière occurrence, il faut adapter l'algorithme ou parcourir ensuite les cases voisines.

Quelle différence avec la recherche dans un arbre binaire de recherche ?

L'idée est la même : à chaque comparaison, on écarte une partie des données. Dans un arbre binaire de recherche, on compare la valeur au nœud courant et on descend dans le fils gauche si elle est inférieure, dans le fils droit si elle est supérieure ³. Le nombre de comparaisons dépend alors de la hauteur de l'arbre ³ ; dans un tableau trié, il dépend du nombre de moitiés successives que l'on peut écarter.

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

La recherche dans une table : cours de NSI en Première

L'essentiel

Chercher dans une table : de quoi parle-t-on ?

La recherche séquentielle (parcours complet)

Rechercher dans une table de lignes

La recherche dichotomique dans un tableau trié

Écrire la dichotomie en Python

Comparer le coût des deux méthodes

Ouverture : l'arbre binaire de recherche

Bilan et erreurs fréquentes

Exercices corrigés

Exercice 1 Dérouler une dichotomie

Exercice 2 Rechercher des élèves dans une table

Exercice 3 Borner le nombre de comparaisons dans un ABR

Quiz

Les questions qu'on se pose

Sources

Primaire

Collège

Lycée

Supérieur

Tour	`debut`	`fin`	`m`	`t[m]`	Décision
1	0	8	4	21	$21 > 10$ : `fin = 3`
2	0	3	1	8	$8 < 10$ : `debut = 2`
3	2	3	2	12	$12 > 10$ : `fin = 1`