Cours : Recherche Séquentielle avec Sentinelle

1) Objectif

La recherche séquentielle consiste à parcourir un tableau du début à la fin pour retrouver un élément x. La version avec sentinelle est une amélioration : on ajoute une case supplémentaire à la fin du tableau et on y place x. Ainsi, la boucle s’arrête toujours sans avoir besoin de tester “fin du tableau” à chaque tour.

2) Principe (idée de la sentinelle)

On a un tableau de N éléments : T[1..N]
On ajoute une case : T[N+1] appelée sentinelle
On met : T[N+1] ← x
On parcourt depuis 1 jusqu’à rencontrer x
Si on trouve x avant la sentinelle, alors x existait dans le tableau. Sinon, si on arrive à N+1, x n’était pas dans le tableau initial.

3) Algorithme en pseudo-code

Algorithme RechercheSentinelle
Const N = 6
Const M = N + 1
Var
  T : tableau[1..M] d'entier
  x : entier
  i : entier
Debut
  Ecrire("Entrer les ", N, " elements du tableau :")
  Pour i de 1 a N Faire
    Lire(T[i])
  FinPour

  Ecrire("Entrer l'element a rechercher :")
  Lire(x)

  T[M] <- x          // sentinelle
  i <- 1

  Tantque (T[i] <> x) Faire
    i <- i + 1
  FinTantque

  Si (i = M) Alors
    Ecrire("Element inexistant dans le tableau.")
  Sinon
    Ecrire("Element existant en position : ", i)
  FinSi
Fin

4) Explication de l’algorithme (comment ça marche)

On lit les éléments dans T[1..N].
On lit la valeur recherchée x.
On place x dans T[N+1] (la sentinelle). Comme ça, même si x n’est pas dans T[1..N], la boucle finira forcément quand elle atteindra T[N+1].
On commence à i = 1 et on avance tant que T[i] ≠ x.
À la fin :
- Si i = N+1 ⇒ x n’était pas dans le tableau initial.
- Sinon ⇒ x a été trouvé en position i.