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 liste | Séquentielle, au pire | Dichotomique, au pire |
|---|---|---|
| 10 | 10 comparaisons | 4 comparaisons |
| 100 | 100 comparaisons | 7 comparaisons |
| 1 000 | 1 000 comparaisons | 10 comparaisons |
| 1 000 000 | 1 000 000 de comparaisons | 20 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
- Deux façons de chercher
- Ce que coûte chaque méthode
- La dichotomie, déroulée
- Quand trier d'abord vaut la peine
Je me teste
Combien de comparaisons au pire pour trouver un élément dans une liste triée de 1000 ?
- Environ 500
- Environ 10
- Environ 1000
Que fait la dichotomie sur une liste non triée ?
- Elle peut répondre faux
- Elle devient simplement plus lente
- Elle refuse de démarrer
Le mot d’Oscar — Cherchez « logarithme » dans le dictionnaire.
Réponses : 1. B · 2. A