Chapitre 13 : Recherche dichotomique.

Introduction :

Chercher un élément dans une liste peut être très long.

Y a-t-il des méthodes plus rapides ?

1. La Recherche Dichotomique

Comment fonctionne la Recherche Dichotomique ?

L'algorithme de recherche dichotomique fonctionne comme suit :

Commencer par définir une plage de recherche qui couvre toute la liste triée.
Calculer l'indice du milieu de la plage de recherche.
Comparer l'élément au milieu avec l'élément recherché. Si les éléments sont égaux, l'élément est trouvé.
Si l'élément au milieu est plus petit que l'élément recherché, la plage de recherche est réduite à la moitié supérieure. Sinon, elle est réduite à la moitié inférieure.
Répéter les étapes 2 à 4 jusqu'à ce que l'élément soit trouvé ou que la plage de recherche devienne vide.

Observe l'animation ci-contre : à chaque comparaison, la moitié de la plage de recherche disparaît.

Vitesse :

Valeur cherchée : ? Comparaisons : 0

plage de recherche élément du milieu éliminé trouvé

d = début de la plage, m = milieu, f = fin de la plage

Clique sur « Démarrer / Redémarrer » pour lancer l'animation.

2. Exercice : recherche dichotomique à la main.

À faire dans le cahier.

On considère la liste suivante : [3, 5, 8, 12, 15, 19, 23, 35, 42, 56, 60, 67, 70, 78, 91]

En faisant une recherche dichotomique :

Écrire dans votre cahier les différentes étapes de la recherche du nombre 70.
Écrire dans votre cahier les différentes étapes de la recherche du nombre 14.

3. Exercice : Recherche dichotomique

Compléter la fonction ci-dessous qui implémente une recherche dichotomique :

Une liste est donnée afin de tester la fonction.

def dichotomie(tab, x): """ tab : tableau d’entiers trié dans l’ordre croissant x : nombre entier La fonction renvoie True si tab contient x et False sinon """ debut = 0 fin = len(tab) - 1 while debut <= fin: m = ... # indice du milieu if x == tab[m]: return ... # trouvé if x > tab[m]: debut = m + 1 # on cherche à droite else: fin = ... # on cherche à gauche return ... # non trouvé liste = [3, 5, 8, 12, 15, 19, 23, 35, 42, 56, 60, 67, 70, 78, 91] element_cherche = 12 if dichotomie(liste, element_cherche): print(f"{element_cherche} est présent dans la liste.") else: print(f"{element_cherche} n'est pas présent dans la liste.")

>>>

4. Correction de la recherche dichotomique

Invariant de boucle

On considère la boucle qui manipule les indices gauche et droite.

Invariant : À chaque itération, si l’élément recherché est présent dans le tableau, alors il se trouve dans l’intervalle d’indices \( [gauche, droite] \).

Initialisation

Au début de l’algorithme, on a :

\( gauche = 0 \) et \( droite = n - 1 \).

L’intervalle \( [gauche, droite] \) contient donc tout le tableau. L’invariant est vrai avant la première itération.

Conservation

À chaque itération, on calcule l’indice milieu et on compare la valeur recherchée avec tab[milieu].

Si tab[milieu] est égal à la valeur recherchée, l’algorithme renvoie immédiatement True.
Si la valeur recherchée est plus petite, on met droite = milieu - 1.
Si elle est plus grande, on met gauche = milieu + 1.

Dans chaque cas, on élimine une moitié du tableau qui ne peut pas contenir la valeur recherchée. L’invariant reste donc vrai après chaque itération.

Terminaison

La boucle s’arrête lorsque gauche > droite.

Dans ce cas, l’intervalle \( [gauche, droite] \) est vide. D’après l’invariant, la valeur recherchée ne peut donc pas être présente dans le tableau.

Conclusion

Si l’algorithme renvoie True, la valeur est bien dans le tableau. S’il termine sans la trouver, alors elle n’y est pas.

La recherche dichotomique est donc un algorithme correct, à condition que le tableau soit trié.