duranton.net

Chapitre 13 : Recherche dichotomique.

Introduction :

La recherche dichotomique, également appelée recherche binaire, est un algorithme de recherche efficace qui permet de trouver rapidement un élément dans un tableau trié en divisant à chaque étape la plage de recherche en deux et en éliminant la moitié inutile.

1. La Recherche Dichotomique

Comment fonctionne la Recherche Dichotomique ?

L'algorithme de recherche dichotomique fonctionne comme suit :

  1. Commencer par définir une plage de recherche qui couvre toute la liste triée.
  2. Calculer l'indice du milieu de la plage de recherche.
  3. Comparer l'élément au milieu avec l'élément recherché. Si les éléments sont égaux, l'élément est trouvé.
  4. 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.
  5. Répéter les étapes 2 à 4 jusqu'à ce que l'élément soit trouvé ou que la plage de recherche devienne vide.

2. Exercice:

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

  1. Ecrire dans votre cahier les différentes étapes de la recherche du nombre 70.
  2. Ecrire 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.")

Tests :

# Tests

Affichage :

Console:


    

      >>>
      
    

  











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


    

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