Sommet d'un tableau unimodal — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 12)

Sommet d'un tableau unimodal

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

Énoncé

Le tableau $T [0 : n]$ (non vide) est strictement croissant jusqu'à un indice $s$ , puis strictement décroissant, comme $[1, 4, 9, 12, 7, 5, 2]$ ( $s = 3$ ). L'une des deux parties peut être vide. Écrire une fonction en $Θ (lo g n)$ qui retourne $s$ , en comparant $T [m]$ à $T [m + 1]$ .

Corrigé

Si $T [m] < T [m + 1]$ , on est dans la montée : le sommet est après $m$ . Sinon on est dans la descente (ou au sommet) : le sommet est en $m$ ou avant. Invariant : « $s \in [g : d + 1]$ », avec $g = 0$ et $d = n - 1$ au départ. Comme $m < d$ , la case $m + 1$ existe toujours.


static int sommet(int[] T) { int n = T.length;
    int g = 0, d = n - 1;
    // I(g,d) : l'indice du maximum est dans [g:d+1]
    while (g < d) {
        int m = g + (d - g) / 2;        // g <= m < d
        if (T[m] < T[m + 1]) g = m + 1; // on monte : s > m
        else d = m;                     // on descend : s <= m
    }
    return g;
}


sommet [1, 4, 9, 12, 7, 5, 2] -> indice 3
sommet [1,2,3] -> 2, [3,2,1] -> 0


nom : T
valeurs : 1 4 9 12 7 5 2
colorier : 3
fleches : 3->4:12>7
pointeurs : g=0 m=3 d=6
zone : 0..3 croissant
zone : 3..6 décroissant
legende : tour 1 : T[m] > T[m+1], on descend : d = m = 3

La dichotomie ne demande pas que le tableau soit trié : elle demande un test qui élimine à coup sûr une moitié de la zone. Complexité $Θ (lo g n)$ .