Tableau trié puis décalé — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 12)

Tableau trié puis décalé

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

Énoncé

Un tableau trié de valeurs distinctes a subi une rotation, par exemple $[11, 15, 1, 3, 6, 8]$ . Écrire une fonction en $Θ (lo g n)$ qui retourne l'indice de sa plus petite valeur. On comparera $T [m]$ à $T [n - 1]$ et on donnera l'invariant.

Corrigé

Notons $s$ l'indice du minimum. Les valeurs de $T [0 : s]$ sont toutes supérieures à $T [n - 1]$ , celles de $T [s : n]$ toutes inférieures ou égales à $T [n - 1]$ . Le test « $T [m] > T [n - 1]$ » dit donc de quel côté de la cassure se trouve $m$ .

Invariant : « l'indice du minimum est dans $[g : d + 1]$ ». Au départ $g = 0$ , $d = n - 1$ . Si $T [m] > T [n - 1]$ , alors $m < s$ et $s \in [m + 1 : d + 1]$ ; sinon $m \geq s$ et $s \in [g : m + 1]$ . On s'arrête quand $g = d$ .


static int indiceMin(int[] T) { int n = T.length;
    int g = 0, d = n - 1;
    // I(g,d) : l'indice du minimum est dans [g:d+1]
    while (g < d) {
        int m = g + (d - g) / 2;        // g <= m < d
        if (T[m] > T[n - 1]) g = m + 1; // m est avant la cassure
        else d = m;                     // m est après la cassure (ou dessus)
    }
    return g;
}


[11, 15, 1, 3, 6, 8] -> 2
[1, 3, 6, 8, 11, 15] -> 0
[15, 1, 3, 6, 8, 11] -> 1
[3, 6, 8, 11, 15, 1] -> 5


nom : T
valeurs : 11 15 1 3 6 8
vert : 2
pointeurs : g=2 d=2
zone : 0..1 > 8
zone : 2..5 au plus 8
legende : T[n-1] = 8 : le test T[m] > 8 dit de quel côté de la cassure est m

La zone $[g : d + 1]$ est divisée par deux à chaque tour : $Θ (lo g n)$ .