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 !!

 

 

Activité
  • Compter le nombre de fois qu’il faudra évaluer la valeur d’une cellule du tableau L  ci-dessous avant d’y trouver la valeur 31 .

  • Quelle est(sont) la(les) valeur(s) du tableau qui demandera(ont) le plus grand nombre d’itérations avant d’être trouvée(s). Et combien d’itérations sont nécessaires ?
Correction

3 itérations sont nécessaires pour trouver la valeur 31 .

 

Et il faudrait 4 itérations pour trouver les valeurs 12 , 13 , 73  ou 80 .

  • Faire de même avec la liste suivante : [1, 2, 5, 7, 8, 12, 13, 14, 19, 20, 25, 26, 28, 30, 35, 39, 50, 52, 63, 64, 81, 90, 98]  et la valeur recherchée 13 .

 

Pseudo code

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

Activité
  • Après exécution de cet algorithme, comment sait-on que la valeur recherchée a été trouvée ?
  • Si la valeur a été trouvée, que vaut son indice dans le tableau ?
Correction

Si la valeur recherchée a été trouvée, alors la condition  L[mil] == v   a été VRAIE, et la variable trv  est donc VRAIE.

L’indice de la valeur recherchée dans le tableau est mil .

 

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.

Définition

Un variant de boucle est une expression :

  • entière
  • positive
  • qui décroît strictement à chaque itération

 

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émentationimplémentation Réalisation d'un produit informatique à partir de documents, mise en œuvre, développement. Codage d'un algorithme dans un langage informatique. en Python

Activité
  • Implémenter l’algorithme de recherche dichotomique en langage Python.

 

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

Vous aimerez aussi...

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

*

code