Aller au contenu
Ludicademy
English
Thème Élan
ClairsSombres
S’inscrire

Fiche de révision : Chercher dans une liste : le parcours et la dichotomie

L’essentiel de la leçon, ce qu’il faut retenir, les pièges et un petit test : une page à relire avant le contrôle.

Ludicademyludicademy.fr · apprendre en jouant, du CP à la Terminale
Fiche de révision · Logique · 1re · algorithmique

Chercher dans une liste : le parcours et la dichotomie

Objectif : pourquoi le dictionnaire ne se lit pas depuis la page 1

L’essentiel

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.

À 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

Le tableau à connaître

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

⚠ Attention, piège

  • 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.

Exemples

  • Liste triée de 1 à 100, on cherche 73. Bornes de départ : bas vaut 1, haut vaut 100.

Le plan de la leçon

  1. Deux façons de chercher
  2. Ce que coûte chaque méthode
  3. La dichotomie, déroulée
  4. Quand trier d'abord vaut la peine

Je me teste

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

    1. Environ 500
    2. Environ 10
    3. Environ 1000
  2. Que fait la dichotomie sur une liste non triée ?

    1. Elle peut répondre faux
    2. Elle devient simplement plus lente
    3. Elle refuse de démarrer

Le mot d’Oscar — Cherchez « logarithme » dans le dictionnaire.

Réponses : 1. B · 2. A

La leçon complète, ses exercices et ses jeux : ludicademy.fr/lecon/2411fiche de révision · usage libre en classe et à la maison

Toutes les fiches de révision : par matière et par classe · les fiches d’exercices : la bibliothèque.