Recherche d’une occurrence

Algorithmique - recherche d'une occurrence

Recherche d’une occurrence 

L’objectif du cours est de présenter un algorithme permettant de savoir si un élément $a$ appartient ou non à un tableau $T$ de taille $n$ non nulle, par balayage. Cette méthode consiste à vérifier successivement toutes les valeurs du tableau jusqu’à ce que la valeur $a$ apparait.

C’est une technique utilisée lors de la résolution par balayage de l’équation $f(x) = 0$ où $f$ est une fonction continue et strictement monotone. 

L’algorithme est le suivant :
$i = 0$
while $i < n$ and $a!= T[i]$:
  $i = i + 1$
endwhile
if $i < n$ disp $i$

Pour comprendre le fonctionnement de l’algorithme, une méthode consiste à regarder pas à pas les étapes à la main. 
Tout d’abord $i$ vaut $0$ donc $i$ est forcément inférieur à $n$ (non nul). L’ordinateur compare ensuite $a$ à $T[0]$. Si $a$ est égal au premier élément de la liste, le programme ne rentre pas dans la boucle et affiche l’indice pour lequel $a$ apparait, c’est à dire $0$.

Sinon, cela signifie que $a$ ne vaut pas $T[0]$. $i$ est alors augmenté de $1$ puis on recommence les différentes comparaisons. Le programme vérifie donc de proche en proche toutes les valeurs du tableau. 

Si $a$ n’appartient pas au tableau, $i$ prend lors de la dernière itération la valeur $n$. La boucle se termine et la condition IF $i < n$ n’est plus remplie : l’algorithme n’affiche donc rien car il n’existe pas d’élément valant $a$.

Ainsi, $i$ prend ses valeurs dans la suite d’entiers croissante $0, 1, 2, … p leq n$ où $a = T[p]$ si $a$ appartient à $T$ et $p = n$ sinon. Dans tous les cas $i$ converge vers une valeur finie, qui assure la terminaison de l’algorithme.

Il apparait aussi le pire des cas en terme de coût : c’est la cas où il faut balayer tout le tableau pour trouver ou non l’élément $a$. Dans ce cas, il y a $n$ comparaisons et $n$ additions, et aussi une comparaison pour l’affichage. Cela correspond ainsi à un coût de $2n +1$. Il s’agit donc d’un algorithme linéaire.