Fiche de cours
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 $