Recherche dichotomique dans une liste triée

Merci !

Fiches
Classe(s) : 1re Générale | Thème(s) : Algorithmes fondamentaux

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] :

05230_chap07_03

Recherche de l’élément 7 dans la liste triée [1, 2, 5, 9, 10, 14, 17, 24, 41] :

05230_chap07_04

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)n est la taille de la liste.

IV Exemple de mise en œuvre

Recherche dichotomique d’un élément dans une liste triée :

PB_Bac_05230_numerique1_TT_p213-244_C07_Groupe_Schema_4

Annabac est gratuit en septembre !

Inscris-toi pour en profiter.