Recherche avec sentinelle — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 12)

Recherche avec sentinelle

Recherche séquentielle, dichotomique, arrière · niveau 1 (application)

Énoncé

Dans la recherche séquentielle, chaque tour de boucle fait deux tests : « la zone n'est-elle pas vide ? » et « la case contient-elle $x$ ? ». On suppose que le tableau a une case supplémentaire $T [n]$ , libre. En y plaçant $x$ (la sentinelle), montrer qu'on peut écrire une boucle à un seul test. Donner l'invariant, le programme et justifier sa terminaison.

Corrigé

On place $x$ en case $n$ : $x$ est alors certainement dans $T [0 : n + 1]$ , et la boucle « tant que $T [i] \neq = x$ » s'arrête au plus tard en $i = n$ . Le test « $i < n$ » devient inutile dans la boucle.

Invariant : « $x$ n'est pas dans $T [0 : i]$ ». Il est vrai pour $i = 0$ ; si $T [i] \neq = x$ , il reste vrai pour $i + 1$ . À l'arrêt $T [i] = x$ : si $i < n$ , c'est la première occurrence de $x$ ; si $i = n$ , on n'a trouvé que la sentinelle, et $x$ n'est pas dans $T [0 : n]$ .


static int rechercheSentinelle(int[] T, int n, int x) { // T a n+1 cases
    T[n] = x;                         // la sentinelle : x est dans T[0:n+1]
    int i = 0;
    // I(i) : x n'est pas dans T[0:i]
    while (T[i] != x) i++;            // s'arrête au plus tard en n
    return i < n ? i : -1;
}


nom : T
valeurs : _ _ _ _ _ _ _ x
indices : 0 1 2 3 4 5 6 n
griser : 0..2
colorier : n
pointeurs : i=3
zone : 0..2 x absent
legende : la sentinelle x en case n arrête la boucle au plus tard en i = n

Terminaison : $n - i$ est un entier positif qui décroît à chaque tour. La complexité reste $Θ (n)$ , mais chaque tour ne fait plus qu'une comparaison au lieu de deux.