Retour

Recherche dichotomique dans un tableau trié

Principe

Cet algorithme compare la valeur recherchée à la valeur du milieu du tableau.

Si c’est la valeur recherchée, on s’arrête et on retourne sa position. Si cette valeur est plus petite, alors la valeur recherchée est située dans la partie gauche du tableau, sinon elle est dans la partie droite. On répète le procédé de comparaison jusqu’à ce que l’on obtienne la valeur recherchée, ou jusqu’à ce que l’on ait réduit l’intervalle de recherche à un intervalle vide : cela signifie que la valeur recherchée n’est pas présente dans le tableau.

À chaque étape, la zone de recherche de la valeur est divisée par deux.

Algorithme

Text Only

//déclarations
 indice_gauche, indice_droite, elmt, indice_centre: Entiers
 liste : liste de N entiers triés
 retour : Booléen

//initialisation
 indice_gauche ← 0 
 indice_droite ← N-1
 retour ← faux

//Boucle de recherche
 // La condition début inférieur ou égal à fin permet d'éviter de faire
 // une boucle infinie si 'val' n'existe pas dans le tableau.
  TANT QUE retour != vrai et indice_gauche <= indice_droite:
      indice_centre ← partie_entière((indice_gauche + indice_droite)/2)
      SI liste[indice_centre] == val:
         retour ← vrai
      SINON:
         SI val > liste[indice_centre]:
            début ← indice_centre+1
         SINON:
            fin ← indice_centre-1
          FIN SI
      FIN SI
  FIN TANT QUE

 //Affichage du résultat
  SI retour == vrai:
      Afficher "La valeur ", val , " est au rang ", indice_centre
  SINON:
      Afficher "La valeur ", val , " n'est pas dans le tableau."
  FIN SI

Implémentation en Python

🐍 Script Python

def dichotomie(liste, val):
  indice_gauche = 0 
  indice_droite = len(liste -1)
  retour = False

  while retour != true and indice_gauche <= indice_droite:
      indice_centre = (indice_gauche + indice_droite)//2
      if liste[indice_centre] == val:
         retour = true
      else:
         if val > liste[indice_centre]:
            debut = indice_centre + 1
         else:
            fin = indice_centre - 1

  if retour == vrai:
      print("La valeur ", val , " est au rang ", indice_centre)
  else:
      print("La valeur ", val , " n'est pas dans le tableau.")

Complexité

Logarithmique

$$ O(log(n)) $$