Recherche dichotomique

Lorsque l’on souhaite rechercher une occurrence  dans un tableau non trié, il faut, dans le pire des cas, le parcourir jusqu’au bout. La complexité est d’ordre \(\mathcal{O}(n)\) (\(n\) étant la taille du tableau).

Si le tableau est déjà trié, on peut employer une technique plus rapide appelée recherche dichotomique.

Algorithme de recherche dichotomique

On cherche dans un tableau L  une valeur v . Un pointeur i  est initialisé au « milieu » du tableau (à 1 près car la taille du tableau est peut-être paire). On a alors 3 cas de figure :

• Si la valeur recherchée et supérieure à la valeur située à l’indice i , cela signifie qu’elle se trouve à un indice entre i  et celui de la dernière valeur du tableau : soit « après » i .
• Si la valeur recherchée et inférieure à la valeur située à l’indice i , cela signifie que la valeur recherché se trouve « avant » l’indice i .

On recommence la même opération avec la « moitié » du tableau qui est sensée contenir la valeur recherchée, jusqu’à ce qu’elle soit trouvée, ou que la liste ne comporte plus qu’un seul élément.

• Si la valeur recherchée et égale à la valeur située à l’indice i , c’est qu’on l’a trouvée !!

 

 

 

Pseudo code

On peut écrire cet algorithme en pseudo-code de la manière suivante :

L : tableau d'entiers trié
mil : nombre entier
fin : nombre entier
deb : nombre entier
v : nombre entier   // la valeur recherchée
trv : booléen 

trv ← FAUX
deb ← 1
fin ← longueur(L)
tant que NON trv ET deb ⩽ fin :
   mil ← partie_entière((deb+fin)/2)
   si L[mil] == v :
      trv ← VRAI
   sinon :
      si v > L[mil] :
         deb ← mil+1
      sinon :
         fin ← mil-1
      fin si
   fin si
fin tant que

 

Terminaison

Cet algorithme comporte une boucle tant que …  , cela signifie que le nombre d’itérations n’est pas connu d’avance et dépend du cas à traiter. Il faut donc impérativement montrer que cet algorithme se termine dans tous les cas (on ne peut pas « tomber dans une boucle infinie »).

Si on donne un indice \(i\) à chaque variable impliquée dans la boucle, \(i\) désignant la i^ème itération. Avant le démarrage de la boucle, on est donc à l’itération \(0\) et :

\(deb_0 = 1\) et \(fin_0 = n\)

À la fin de la première itération de la boucle, nous aurons \(fin_1\) et \(deb_1\)…

On définit aussi : \(mil_i = \frac{deb_i + fin_i}{2}\)

À la fin de l’itération \(k\) nous avons uniquement plusieurs cas de figure :

• si \(L[mil_k] = v\) : l’algorithme se termine, car une des conditions pour continuer la boucle devient fausse : trv ← VRAI et par conséquent NON trv  est FAUX
• sinon
  • si \(deb_k > fin_k\) : l’algorithme se termine, car l’autre condition pour continuer la boucle devient fausse : deb ⩽ fin 
  • sinon (\(deb_k ⩽ fin_k\)) :
    • si \(v > L[mil_k]\) : on « entre » dans la boucle : \(deb_{k+1} = mil_k + 1\) et \(fin_{k+1} = fin_k\).
      On a alors \(fin_{k+1} – deb_{k+1} < fin_k – deb_k\)
    • sinon (\(v ⩽ L[mil_k]\)) : on « entre » dans la boucle : \(deb_{k+1} = deb_k\) et \(fin_{k+1} = mil_k – 1\).
      On a alors \(fin_{k+1} – deb_{k+1} < fin_k – deb_k\)

 

Remarques :

• chacune des alternatives ci-dessus est exclusive (si … sinon …). Cela signifie qu’il n’y en a pas d’autre !
• Quel que soit le cas, nous avons \(fin_{k+1} – deb_{k+1} < fin_k – deb_k\), nous pouvons donc dire que \(fin_i – deb_i\) est strictement décroissante.

 

\(fin_i – deb_i\) est appelé un variant de boucle.

 

Complexité

Le calcul de la complexité doit bien entendu se faire dans le cas le plus défavorable : la valeur recherchée n’est pas dans le tableau !

Soit un tableau de taille \(n\).

Si on « coupe » ce tableau en deux parts égales, cela revient à diviser \(n\) par deux à chaque itération :

\(n_1=\frac{n}{2}\), \(n_2=\frac{n_1}{2}\), …

Puisque la taille d’un tableau est forcément un nombre entier, il va immanquablement se produire que \(n_i\) deviendra égal à 1. Cela signifiera qu’après avoir divisé \(n\) par 2 un nombre de fois égal à un certain nombre \(a\), le tableau ne comportera plus qu’une seule valeur (et par conséquent l’algorithme s’arrête).

\(n_i=1=\frac{n}{2\times 2\times 2 …\times 2}=\frac{n}{2^a}\)

Soit : \(a=\log_2\left(n\right)\)

On en déduit l’ordre de complexité de l’algorithme de recherche dichotomique :

\(\mathcal{O}\left(\log_2(n)\right)\)

 

 

Implémentation en Python

 

source : https://pixees.fr/informatiquelycee/n_site/nsi_prem_dicho_algo.html