Dernière occurrence et nombre d'occurrences — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 12)

Dernière occurrence et nombre d'occurrences

Recherche séquentielle, dichotomique, arrière · niveau 2

Énoncé

Écrire une fonction int dernierIndice(int[] T, int x) qui retourne, en $Θ (lo g n)$ , le plus petit indice $i$ tel que toutes les valeurs de $T [i : n]$ sont strictement supérieures à $x$ ( $T$ est trié par ordre croissant). On donnera l'invariant. En déduire une fonction qui compte les occurrences de $x$ dans $T$ en $Θ (lo g n)$ .

Corrigé

On recopie premierIndice en remplaçant « $< x$ » par « $\leq x$ ». L'invariant est

$I (g, d) : T [0 : g] \leq x et T [d : n] > x .$

Il est vrai pour $g = 0$ , $d = n$ (deux sous-tableaux vides). Si $T [m] \leq x$ , comme $T$ est trié, $T [0 : m + 1] \leq x$ : $I (m + 1, d)$ est vrai. Sinon $T [m : n] > x$ : $I (g, m)$ est vrai. À l'arrêt, $g = d$ et $T [0 : g] \leq x < T [g : n]$ .


static int dernierIndice(int[] T, int x) { int n = T.length;
    int g = 0, d = n;
    // I(g,d) : T[0:g] <= x  et  T[d:n] > x
    while (g < d) {
        int m = g + (d - g) / 2;      // g <= m < d
        if (T[m] <= x) g = m + 1;     // T[0:m+1] <= x : I(m+1,d)
        else d = m;                   // T[m:n] > x    : I(g,m)
    }
    return g;                         // T[0:g] <= x < T[g:n]
}

static int nbOccurrences(int[] T, int x) {
    return dernierIndice(T, x) - premierIndice(T, x);
}

Les occurrences de $x$ forment le sous-tableau $T [premierIndice : dernierIndice]$ : leur nombre est la différence des deux indices. Avec $S = [1, 3, 3, 3, 6, 8, 11, 15]$ :


dernierIndice(S,3)=4 nbOcc(3)=3 nbOcc(7)=0 nbOcc(15)=1 nbOcc(0)=0


nom : S
valeurs : 1 3 3 3 6 8 11 15
colorier : 1..3
zone : 0..0 < 3
zone : 1..3 = 3
zone : 4..7 > 3
legende : premierIndice = 1, dernierIndice = 4 : 4 - 1 = 3 occurrences

Deux dichotomies : $Θ (lo g n)$ , alors qu'un comptage séquentiel est en $Θ (n)$ .