Médiane de deux tableaux triés de même taille

Définition On considère deux tableaux triés A et B, chacun de taille n. Après fusion, on obtient un tableau trié de taille 2n. Le problème consiste à déterminer la médiane de ce tableau fusionné.

La médiane d’un tableau trié est la valeur centrale. Lorsque le nombre total d’éléments est pair, la médiane est la moyenne des deux éléments du milieu.

Remarque Ici, le tableau final contient 2n éléments. Comme 2n est pair, la médiane est donc la moyenne des éléments situés aux positions n-1 et n dans le tableau fusionné (en indexation à partir de 0).

Problème

Écrire un programme qui reçoit deux tableaux triés A et B de taille n et qui calcule la médiane du tableau obtenu après leur fusion.

Contraintes

Les deux tableaux sont triés dans l’ordre croissant
Les deux tableaux ont la même taille n
La médiane finale est calculée sur 2n éléments

Exemple

Exemple illustratif

Tableaux

A = [3, 5, 7, 8, 11, 12]
B = [2, 4, 6, 9, 17, 22]

Fusion triée

[2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 17, 22]

Explication : les deux valeurs centrales sont 7 et 8, donc la médiane vaut (7 + 8) / 2 = 7 en division entière, ou 7.5 en division réelle selon le type de retour choisi.

Attention Dans plusieurs implémentations proposées ci-dessous, le résultat est calculé avec une division entière. Si la somme des deux valeurs centrales est impaire, la partie décimale sera perdue.

Méthode 1 : idée de fusion

La première méthode consiste à s’inspirer de la procédure de fusion utilisée dans le tri fusion. On parcourt simultanément les deux tableaux triés, en avançant toujours dans celui qui possède le plus petit élément courant.

Il n’est pas nécessaire de construire tout le tableau fusionné. Il suffit de mémoriser les deux dernières valeurs rencontrées au moment où l’on atteint le centre du tableau final.

Principe Comme le tableau fusionné contient 2n éléments, il suffit de suivre la fusion jusqu’au rang n. Les deux valeurs importantes sont alors celles des positions n-1 et n.

Idée clé

Pourquoi cette méthode fonctionne ?

Niveau : Débutant

Puisque les deux tableaux sont déjà triés, la procédure de fusion permet de produire les éléments du tableau final dans l’ordre croissant sans effectuer de tri supplémentaire. On peut donc repérer directement les éléments centraux au fur et à mesure.

class Test {

    static int mediane(int tab1[], int tab2[], int n) {
        int i = 0;
        int j = 0;
        int compteur;
        int m1 = -1, m2 = -1;

        /*
         * Comme il y a 2n éléments au total,
         * la médiane est la moyenne des éléments
         * d'indices n-1 et n dans le tableau fusionné.
         */
        for (compteur = 0; compteur <= n; compteur++) {
            if (tab1[i] < tab2[j]) {
                m1 = m2;
                m2 = tab1[i];
                i++;
            } else {
                m1 = m2;
                m2 = tab2[j];
                j++;
            }
        }

        return (m1 + m2) / 2;
    }

    public static void main(String[] args) {
        int A[] = {3, 5, 7, 8, 11, 12};
        int B[] = {2, 4, 6, 9, 17, 22};

        System.out.println("La médiane est " + mediane(A, B, 6));
    }
}

#include <stdio.h>

int mediane(int tab1[], int tab2[], int n)
{
    int i = 0;
    int j = 0;
    int compteur;
    int m1 = -1, m2 = -1;

    /*
        Comme il y a 2n éléments au total,
        la médiane est la moyenne des éléments
        d'indices n-1 et n dans le tableau fusionné.
    */
    for (compteur = 0; compteur <= n; compteur++)
    {
        if (tab1[i] < tab2[j])
        {
            m1 = m2;
            m2 = tab1[i];
            i++;
        }
        else
        {
            m1 = m2;
            m2 = tab2[j];
            j++;
        }
    }

    return (m1 + m2) / 2;
}

int main()
{
    int A[] = {3, 5, 7, 8, 11, 12};
    int B[] = {2, 4, 6, 9, 17, 22};

    printf("La médiane est %d", mediane(A, B, 6));
    return 0;
}

def mediane(tab1, tab2, n):
    i = 0
    j = 0
    m1 = -1
    m2 = -1

    # Comme il y a 2n éléments,
    # la médiane est la moyenne des éléments
    # d'indices n-1 et n dans le tableau fusionné.
    compteur = 0
    while compteur < n + 1:
        compteur += 1

        if tab1[i] < tab2[j]:
            m1 = m2
            m2 = tab1[i]
            i += 1
        else:
            m1 = m2
            m2 = tab2[j]
            j += 1

    return (m1 + m2) // 2


A = [3, 5, 7, 8, 11, 12]
B = [2, 4, 6, 9, 17, 22]
print("La médiane est", mediane(A, B, 6))

Méthode	Complexité temporelle	Complexité spatiale	Idée principale
Fusion partielle	`O(n)`	`O(1)`	Simuler la fusion sans construire tout le tableau

Conseil pratique Cette méthode est simple à comprendre et à programmer. Elle constitue souvent la meilleure première approche avant de chercher une solution plus rapide.

Méthode 2 : diviser pour régner

Une seconde méthode plus efficace repose sur le paradigme Diviser pour régner. L’idée est de comparer les médianes des deux tableaux triés puis d’éliminer, à chaque étape, une moitié de données qui ne peut pas contenir la médiane finale.

Idée générale Soient m1 la médiane de A et m2 la médiane de B.
- Si m1 = m2, alors cette valeur est la médiane recherchée.
- Si m1 < m2, alors la médiane globale se trouve dans la seconde moitié de A et la première moitié de B.
- Si m1 > m2, alors la médiane globale se trouve dans la première moitié de A et la seconde moitié de B.

Procédure

Calculer les médianes m1 et m2 des tableaux A et B.
Si m1 = m2, retourner cette valeur.
Si m1 < m2, continuer la recherche sur la seconde moitié de A et la première moitié de B.
Si m1 > m2, continuer la recherche sur la première moitié de A et la seconde moitié de B.
Arrêter lorsque la taille des sous-tableaux devient petite, par exemple 1 ou 2.
Dans le cas de deux éléments, utiliser la formule : $$ \text{Médiane} = \frac{\max(A[0], B[0]) + \min(A[1], B[1])}{2} $$

Attention Cette méthode suppose que les deux tableaux sont triés et de même taille. Elle est plus subtile à programmer, mais elle réduit fortement le nombre de comparaisons.

Cas de base

Taille	Résultat
`n = 1`	`(A[0] + B[0]) / 2`
`n = 2`	`(max(A[0], B[0]) + min(A[1], B[1])) / 2`

class Test {

    static int getMediane(int[] A, int[] B, int debutA, int debutB, int finA, int finB) {
        if (finA - debutA == 1) {
            return (Math.max(A[debutA], B[debutB]) + Math.min(A[finA], B[finB])) / 2;
        }

        int m1 = mediane(A, debutA, finA);
        int m2 = mediane(B, debutB, finB);

        if (m1 == m2) {
            return m1;
        }
        else if (m1 < m2) {
            return getMediane(A, B, (finA + debutA + 1) / 2, debutB, finA, (finB + debutB + 1) / 2);
        }
        else {
            return getMediane(A, B, debutA, (finB + debutB + 1) / 2, (finA + debutA + 1) / 2, finB);
        }
    }

    static int mediane(int[] tab, int debut, int fin) {
        int n = fin - debut + 1;
        if (n % 2 == 0) {
            return (tab[debut + (n / 2)] + tab[debut + (n / 2 - 1)]) / 2;
        } else {
            return tab[debut + n / 2];
        }
    }

    public static void main(String[] args) {
        int A[] = {3, 5, 7, 8, 11, 12};
        int B[] = {2, 4, 6, 9, 17, 22};

        System.out.println("La médiane est " + getMediane(A, B, 0, 0, 5, 5));
    }
}

#include <stdio.h>

int max(int a, int b)
{
    return a > b ? a : b;
}

int min(int a, int b)
{
    return a < b ? a : b;
}

int mediane(int tab[], int n)
{
    if (n % 2 == 0)
        return (tab[n / 2] + tab[n / 2 - 1]) / 2;
    else
        return tab[n / 2];
}

int getMediane(int A[], int B[], int n)
{
    if (n <= 0)
        return -1;
    if (n == 1)
        return (A[0] + B[0]) / 2;
    if (n == 2)
        return (max(A[0], B[0]) + min(A[1], B[1])) / 2;

    int m1 = mediane(A, n);
    int m2 = mediane(B, n);

    if (m1 == m2)
        return m1;

    if (m1 < m2)
    {
        if (n % 2 == 0)
            return getMediane(A + n / 2 - 1, B, n - n / 2 + 1);
        return getMediane(A + n / 2, B, n - n / 2);
    }

    if (n % 2 == 0)
        return getMediane(B + n / 2 - 1, A, n - n / 2 + 1);

    return getMediane(B + n / 2, A, n - n / 2);
}

int main()
{
    int A[] = {3, 5, 7, 8, 11, 12};
    int B[] = {2, 4, 6, 9, 17, 22};

    printf("La médiane est %d", getMediane(A, B, 6));
    return 0;
}

def mediane(tab, n):
    if n % 2 == 0:
        return (tab[n // 2] + tab[n // 2 - 1]) / 2
    else:
        return tab[n // 2]


def getMediane(A, B, n):
    if n == 0:
        return -1

    elif n == 1:
        return (A[0] + B[0]) / 2

    elif n == 2:
        return (max(A[0], B[0]) + min(A[1], B[1])) // 2

    else:
        m1 = mediane(A, n)
        m2 = mediane(B, n)

        if m1 > m2:
            if n % 2 == 0:
                return getMediane(A[:n // 2 + 1],
                                  B[n // 2 - 1:], n // 2 + 1)
            else:
                return getMediane(A[:n // 2 + 1],
                                  B[n // 2:], n // 2 + 1)

        else:
            if n % 2 == 0:
                return getMediane(A[n // 2 - 1:],
                                  B[:n // 2 + 1], n // 2 + 1)
            else:
                return getMediane(A[n // 2:],
                                  B[:n // 2 + 1], n // 2 + 1)


A = [3, 5, 7, 8, 11, 12]
B = [2, 4, 6, 10, 17, 22]
print("La médiane est", getMediane(A, B, 6))

Méthode	Complexité temporelle	Complexité spatiale	Avantage
Diviser pour régner	`O(log n)`	Dépend de l’implémentation	Beaucoup plus rapide pour de grandes tailles

Comparaison des deux méthodes

Méthode	Complexité	Difficulté d’implémentation	Remarque
Fusion partielle	`O(n)`	Simple	Bonne méthode pour débuter
Diviser pour régner	`O(log n)`	Plus délicate	Plus efficace sur les grands tableaux

Sortie

// La sortie apparaîtra ici…

Prêt · Ctrl+Entrée pour exécuter

Médiane de deux tableaux triés de même taille

Problème

Exemple

Méthode 1 : idée de fusion

Pourquoi cette méthode fonctionne ?

Méthode 2 : diviser pour régner

Procédure

Cas de base

Comparaison des deux méthodes

Discussion (0)

Laisser un commentaire

Structures de données

Algorithmes

Programmation

Bases de données

CPGE

Modules informatique

Médiane de deux tableaux triés de même taille

Problème

Exemple

Méthode 1 : idée de fusion

Pourquoi cette méthode fonctionne ?

Méthode 2 : diviser pour régner

Procédure

Cas de base

Comparaison des deux méthodes

Discussion (0)

Laisser un commentaire