Première > Numérique et sciences informatiques > Algorithmique > Recherche d'une occurrence

RECHERCHE D'UNE OCCURRENCE

Accède gratuitement à cette vidéo pendant 7 jours

Profite de ce cours et de tout le programme de ta classe avec l'essai gratuit de 7 jours !

Démarrer l'essai gratuit

Algorithmique - recherche d'une occurrence

Permalien

Télécharger la fiche de cours Les téléchargements sont réservés uniquements aux abonnés

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.