Étant donné deux tableaux triés arrA et arrB de tailles respectives lenA et lenB, l'objectif est de déterminer leur médiane avec une complexité temporelle de O(log(lenA + lenB)). On suppose que les tableaux ne sont pas simultanément vides.

Exemple :
Entrée : arrA = [1, 3], arrB = [2]
Sortie : La médiane est 2.0

Approches algorithmiques

1. Fusion par fusion (méthode de fusion)

Puisque les tableaux sont triés, on peut les fusionner en un tableau auxiliaire merged. Ensuite, extraire la médiane de ce tableau fusionné est simple. Cette méthode nécessite cependant un espace mémoire supplémentaire pour stocker le tableau fusionné.

Complexité : temps O(lenA + lenB), espace O(lenA + lenB).

2. Méthode des deux pointeurs

Définir deux pointeurs respectivement au début de chaque tableau. Si le nombre total d'éléments total est impair, chercher le (total/2 + 1)-ème élément ; si total est pair, chercher la moyenne du (total/2)-ème et du (total/2 + 1)-ème élément.

Complexité : temps O(lenA + lenB), espace O(1).

3. Recherche binaire (méthode de diviser pour régner)

Les algorithmes en O(log n) s'appuient généralement sur la division du problème. Ici, on réduit la recherche de la médiane à la recherche du k-ième élément des deux tbaleaux triés, où k = (lenA + lenB) / 2. Pour trouver le k-ième élément, on compare les (k/2)-èmes éléments de chaque tableau : si l'élément du premier tableau est inférieur, le k-ième élément se trouve dans la moitié droite de ce tableau ou dans la moitié gauche de l'autre, réduisant ainsi la taille du problème de moitié. On applique récursviement.

Complexité : temps O(log(lenA + lenB)), espace O(1).

Implémentations

Fusion par fusion

class Solution {
    public double findMedianSortedArrays(int[] arrA, int[] arrB) {
        int lenA = arrA.length;
        int lenB = arrB.length;
        int idxA = 0;
        int idxB = 0;
        int pos = 0;
        int[] merged = new int[lenA + lenB];
        while (idxA < lenA && idxB < lenB) {
            merged[pos++] = arrA[idxA] <= arrB[idxB] ? arrA[idxA++] : arrB[idxB++];
        }
        while (idxA < lenA) {
            merged[pos++] = arrA[idxA++];
        }
        while (idxB < lenB) {
            merged[pos++] = arrB[idxB++];
        }
        int total = merged.length;
        if (total % 2 == 0) {
            return (merged[total / 2 - 1] + merged[total / 2]) / 2.0;
        } else {
            return merged[total / 2] * 1.0;
        }
    }
}

Recherche binaire

class Solution {
    public double findMedianSortedArrays(int[] arrA, int[] arrB) {
        int lenA = arrA.length;
        int lenB = arrB.length;
        if (lenA == 0) {
            if (lenB % 2 != 0) {
                return 1.0 * arrB[lenB / 2];
            }
            return (arrB[lenB / 2 - 1] + arrB[lenB / 2]) / 2.0;
        }
        if (lenB == 0) {
            if (lenA % 2 != 0) {
                return 1.0 * arrA[lenA / 2];
            }
            return (arrA[lenA / 2 - 1] + arrA[lenA / 2]) / 2.0;
        }
        int total = lenA + lenB;
        if ((total & 1) == 1) {
            return searchKth(arrA, 0, arrB, 0, total / 2 + 1);
        }
        double first = searchKth(arrA, 0, arrB, 0, total / 2);
        double second = searchKth(arrA, 0, arrB, 0, total / 2 + 1);
        return (first + second) / 2.0;
    }

    private double searchKth(int[] arrA, int startA, int[] arrB, int startB, int k) {
        if (startA >= arrA.length) {
            return arrB[startB + k - 1];
        }
        if (startB >= arrB.length) {
            return arrA[startA + k - 1];
        }
        if (k == 1) {
            return Math.min(arrA[startA], arrB[startB]);
        }
        int half = k / 2;
        int midValA = Integer.MAX_VALUE;
        int midValB = Integer.MAX_VALUE;
        if (startA + half - 1 < arrA.length) {
            midValA = arrA[startA + half - 1];
        }
        if (startB + half - 1 < arrB.length) {
            midValB = arrB[startB + half - 1];
        }
        if (midValA < midValB) {
            return searchKth(arrA, startA + half, arrB, startB, k - half);
        }
        return searchKth(arrA, startA, arrB, startB + half, k - half);
    }
}