Aller au contenu
Ludicademy
Français
Thème Élan
ClairsSombres
S’inscrire
1re · Algorithmique

Chercher dans une liste : le parcours et la dichotomie

pourquoi le dictionnaire ne se lit pas depuis la page 1

≈ 4 min de lecture · palier 1re · trois questions à la fin

Rédigé avec l’aide d’une IA, relu et corrigé par l’équipe Ludicademy · mis à jour le 19 septembre 2026 · Notre méthode

En bref
  • La recherche séquentielle marche sur toute liste et coûte au pire autant que sa taille
  • La dichotomie divise l'intervalle par deux à chaque comparaison : 20 suffisent pour un million
  • Elle exige une liste triée, faute de quoi elle donne une réponse FAUSSE et non lente

Deux façons de chercher

Chercher un élément dans une liste admet deux algorithmes, et le second n'est utilisable qu'à une condition précise.

La RECHERCHE SÉQUENTIELLE lit les éléments un par un depuis le début et s'arrête dès qu'elle trouve. Elle marche toujours, sur n'importe quelle liste. Au pire, elle lit tout : n éléments, n comparaisons.

La RECHERCHE DICHOTOMIQUE regarde l'élément du MILIEU, le compare à la cible, et élimine d'un coup la moitié qui ne peut pas la contenir. Elle recommence sur la moitié restante. Elle exige que la liste soit TRIÉE — sans quoi éliminer une moitié n'a aucun sens.

Ce que coûte chaque méthode

Taille de la listeSéquentielle, au pireDichotomique, au pire
1010 comparaisons4 comparaisons
100100 comparaisons7 comparaisons
1 0001 000 comparaisons10 comparaisons
1 000 0001 000 000 de comparaisons20 comparaisons

La dichotomie, déroulée

La dernière ligne du tableau paraît irréelle. Elle ne l'est pas : chaque comparaison divise le travail restant par deux, et vingt divisions par deux ramènent un million à un.Liste triée de 1 à 100, on cherche 73. Bornes de départ : bas vaut 1, haut vaut 100. Tour 1 — milieu 50. 73 est plus grand : on garde 51 à 100. Tour 2 — milieu 75. 73 est plus petit : on garde 51 à 74. Tour 3 — milieu 62. 73 est plus grand : on garde 63 à 74. Tour 4 — milieu 68. Plus grand : on garde 69 à 74. Tour 5 — milieu 71. Plus grand : on garde 72 à 74. Tour 6 — milieu 73. Trouvé. Six comparaisons contre soixante-treize pour le parcours. Et l'on remarque que rien ne dépend de la valeur cherchée : c'est la TAILLE de l'intervalle, divisée par deux à chaque tour, qui pilote tout.

Sur une liste NON TRIÉE, la dichotomie ne se contente pas d'être lente : elle est FAUSSE. Elle répond « absent » pour un élément présent, parce qu'elle a éliminé la moitié où il se trouvait. Un algorithme qui exige une condition et ne la vérifie pas ne plante pas — il ment.

Quand trier d'abord vaut la peine

Trier coûte cher, bien plus qu'une recherche séquentielle. Pour UNE recherche unique dans une liste quelconque, le parcours gagne. Pour DES MILLIERS de recherches dans la même liste, on trie une fois et l'on gagne ensuite à chaque interrogation. C'est le calcul que fait tout annuaire, tout dictionnaire, tout index de base de données : le coût du rangement est payé une fois, l'économie est encaissée toujours.

OscarCherchez « logarithme » dans le dictionnaire.
SkeletJ'ouvre au milieu. Lettre M. C'est après L, je recule.
OscarVous venez de faire une dichotomie sans y penser.
SkeletPersonne ne lit un dictionnaire depuis la page 1.
OscarPersonne, non. Parce qu'il est TRIÉ. Mélangez-le, et vous n'aurez plus que la page 1 pour commencer.
À retenir
  • La recherche séquentielle marche sur toute liste et coûte au pire autant que sa taille
  • La dichotomie divise l'intervalle par deux à chaque comparaison : 20 suffisent pour un million
  • Elle exige une liste triée, faute de quoi elle donne une réponse FAUSSE et non lente
  • Trier d'abord ne vaut le coup que si l'on cherchera souvent dans la même liste
Exercice

Combien de comparaisons au pire pour trouver un élément dans une liste triée de 1000 ?

Chaque comparaison divise par deux : dix divisions ramènent mille à un.

Exercice

Que fait la dichotomie sur une liste non triée ?

Elle élimine une moitié sans raison valable, et déclare absent un élément qui s'y trouvait.

Expressions à emporter

Expression Traduction
recherche séquentiellelire un par un depuis le début
dichotomieéliminer une moitié à chaque comparaison
prérequisla condition qu'un algorithme exige sans la vérifier

Maintenant, jouez-la

Trois questions pour voir

La règle est lue. Voyons si elle est entrée : trois questions, ici même, sans compte.

6 exercices corrigés de logique en 1re → sans compte, corrigés à chaque réponse

La règle est lue ; il reste à la faire entrer. Trois minutes suffisent.

Jouer « le pont de cordes » → Quiz Express · sans compte

Ou choisissez votre salle :

Et côté jeux de société : 🎪 Échecs → les règles d'échecs

Sur papier : 🖨️ La fiche de cette leçon

Pour réviser : 📝 La fiche de révision

Toutes les leçons 1re