Rédigé avec l’aide d’une IA, relu et corrigé par l’équipe Ludicademy · mis à jour le 19 septembre 2026 · Notre méthode
- 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 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 |
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.

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.





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



