La recherche d’un élément dans une liste fait partie des problèmes récurrents. Lorsque la liste est triée, la recherche dichotomique est beaucoup plus rapide que la recherche séquentielle.
I. Problème posé
Nous voulons rechercher l’élément 7 dans la liste [1, 2, 5, 9, 10, 14, 17, 24, 41].
Avec une recherche séquentielle ou recherche par balayage, on parcourt la liste du début à la fin en comparant chaque valeur à l’élément recherché. Dans le pire des cas, on parcourt la liste en entier. Dans notre exemple, il faut faire 9 comparaisons.
Mot clé
Le nom dichotomie provient du grec ancien dikhotomia qui signifie « couper en deux ».
Comme la liste de départ est triée, la recherche dichotomique permet d’améliorer la performance de la recherche.
II. Principe de la recherche dichotomique
Voici le principe de la recherche dichotomique avec une liste triée dans l’ordre croissant :
• Si la liste est vide : répondre négativement, la recherche est finie.
• Sinon, trouver la valeur la plus centrale de la liste et comparer cette valeur à l’élément recherché :
- si la valeur est celle cherchée : répondre positivement, la recherche est finie ;
- si la valeur est strictement plus petite que l’élément recherché, reprendre la procédure avec la seconde moitié de la liste ;
- sinon reprendre la procédure avec la première moitié de la liste.
Exemple : Recherche de l’élément 5 dans la liste triée [1, 2, 5, 9, 10, 14, 17, 24, 41] :
Recherche de l’élément 7 dans la liste triée [1, 2, 5, 9, 10, 14, 17, 24, 41] :
Il suffit de 4 tours de boucle pour conclure qu’un élément n’est pas dans une liste de taille 9.
III. Nombre de tours de boucle maximum
|
Taille de la liste |
0 |
1 |
2 |
4 |
8 |
16 |
32 |
64 |
128 |
N |
|
Recherche séquentielle |
0 |
1 |
2 |
4 |
8 |
16 |
32 |
64 |
128 |
N |
|
Recherche dichotomique |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
log2N |
Le nombre de tours de boucle de la recherche dichotomique est donc de l’ordre de log2(n) où n est la taille de la liste.
IV. Exemple de mise en œuvre
Recherche dichotomique d’un élément dans une liste triée :
