Chercher dans 10 éléments : la dichotomie en vaut-elle la peine ?
Pour 10 éléments, la dichotomie demande 4 étapes contre 10 au pire : l'écart est modeste.
Par Jimenez Julien, éditeur de Calepin Binaire · mis à jour le
- Dichotomie, pire cas
- 4 étapes
- Recherche linéaire, pire cas
- 10 étapes
- Recherche linéaire, cas moyen
- 6 étapes
- Gain au pire cas
- × 2,5
La dichotomie suppose une liste déjà triée.
Le cas en détail
Sur de petites listes, la différence est peu visible, et trier la liste d'abord coûte du temps. Un parcours simple est souvent plus clair et suffisamment rapide. La complexité se mesure sur de grandes tailles.
À retenir : N'optimisez pas ce qui ne pose pas de problème : la lisibilité compte autant que la vitesse.
L'exemple chiffré
Valeurs utilisées dans ce cas (des exemples, pas des mesures) :
- Nombre d'éléments de la liste triée : 10
- Dichotomie, pire cas
- 4 étapes
- Recherche linéaire, pire cas
- 10 étapes
- Recherche linéaire, cas moyen
- 6 étapes
- Gain au pire cas
- × 2,5
La dichotomie suppose une liste déjà triée.
Modifiez les champs ci-dessus pour adapter le calcul à votre situation : le résultat se met à jour tout de suite.
Comment ça se calcule
La recherche dichotomique compare l'élément cherché au milieu de la liste triée et élimine la moitié à chaque étape : au pire, il faut plancher(log2 n) + 1 étapes. La recherche linéaire parcourt la liste : au pire n étapes, en moyenne environ n / 2 si l'élément est présent.
Les résultats sont fournis à titre indicatif, sans valeur de conseil juridique, fiscal ou financier.