Cours Stage - Recherche d'une occurence

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

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. 

Il reste 70% de cette fiche de cours à lire
Cette fiche de cours est réservée uniquement à nos abonnés. N'attends pas pour en profiter, abonne-toi sur lesbonsprofs.com. Tu pourras en plus accéder à l'intégralité des rappels de cours en vidéo ainsi qu'à des QCM et des exercices d'entraînement avec corrigé en texte et en vidéo.