Maximum par moitiés, minimum et maximum

-

static int max(int[] T, int i, int j) { // T[i:j] non vide
    if (j - i == 1) return T[i];
    int k = (i + j) / 2;              // i < k < j : deux moitiés non vides
    int a = max(T, i, k), b = max(T, k, j);
    return a >= b ? a : b;            // une comparaison
}

Le nombre de comparaisons vérifie $c(1)=0$ et $c(n)=c(\lfloor n/2\rfloor )+c(\lceil n/2\rceil )+1$, d'où $c(n)=n-1$ (récurrence immédiate) : autant qu'un parcours séquentiel. Sur un tableau de $10$ valeurs, le programme compte $9$ comparaisons.

• On prend les valeurs par paires $(a,b)$ : une comparaison les ordonne, puis le plus petit défie le minimum et le plus grand défie le maximum. Trois comparaisons pour deux valeurs, au lieu de quatre.

static int[] minMax(int[] T) { int n = T.length;
    int mn, mx, k;
    if (n % 2 == 0) {
        if (T[0] < T[1]) { mn = T[0]; mx = T[1]; } else { mn = T[1]; mx = T[0]; }
        k = 2;
    } else { mn = mx = T[0]; k = 1; }
    // I(k) : mn et mx sont le min et le max de T[0:k], et n - k est pair
    while (k < n) {
        int a = T[k], b = T[k + 1];
        if (a > b) { int t = a; a = b; b = t; } // a <= b
        if (a < mn) mn = a;
        if (b > mx) mx = b;
        k = k + 2;
    }
    return new int[] {mn, mx};
}

n=10 : minMax correct=true, 13 comparaisons (3n/2 = 15)
n=1000 : minMax correct=true, 1498 comparaisons (3n/2 = 1500)
n=1001 : minMax correct=true, 1500 comparaisons (3n/2 = 1501)

On fait $\lceil 3n/2\rceil -2$ comparaisons, contre $2n-2$ pour deux parcours séparés.