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

  1. Accueil
  2. Cours & problèmes
Dernières actualités
Le moyen le plus simple pour apprendre les réseaux informatiques
Langage SQL - Guide complet avec des exercices corrigés
Langage Python - Guide complet avec des exercices corrigés
Langage C++- Guide complet avec des exercices corrigés

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

Etant donné deux tableaux triés A et B de taille n chacun, le problème est de trouver la médiane du tableau obtenu après la fusion des deux tableaux (c'est-à-dire un tableau de longueur 2n).

 Remarque ! La médiane est une valeur présente au centre d'un tableau trié.
Exemple : 

 Remarque ! Puisque la taille du tableau fusionné est paire (2n), nous devons prendre une moyenne des deux nombres du milieu et retourner la moyenne.

Méthode 1 - Idée de tri par fusion

Utilisez la procédure de fusion du tri par fusion. Gardez une trace du nombre compteur tout en comparant les éléments de deux tableaux. Si compteur devient n (pour 2n éléments), nous avons atteint la médiane. Prenez la moyenne des éléments aux indices n-1 et n dans le tableau fusionné.

Solution : 
class Test {

    // Calculer la médiane
    static int Mediane(int tab1[], int tab2[], int n) {
        int i = 0;
        int j = 0;
        int compteur;
        int m1 = -1, m2 = -1;

        /*
         * Puisqu'il y a 2n éléments, la médiane sera la moyenne des éléments à l'indice
         * n-1 et n dans le tableau obtenus après la fusion de tab1 et tab2
         */
        for (compteur = 0; compteur <= n; compteur++) {

            if (tab1[i] < tab2[j]) {
                // Stocker m2 dans m1 (déclage)
                m1 = m2;
                m2 = tab1[i];
                i++;
            } else {
                // Stocker m2 dans m1 (déclage)
                m1 = m2;
                m2 = tab2[j];
                j++;
            }
        }

        return (m1 + m2) / 2;
    }

    /* Fonction principale */
    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; // indice actuel de tab1
    int j = 0; // indice actuel de tab2
    int compteur;
    int m1 = -1, m2 = -1; // m1=element 1, m2=element 2 ; mediane = (m1+m2)/2

    /* 
        Puisqu'il y a 2n éléments, la médiane sera la moyenne des éléments 
        à l'indice n-1 et n dans le tableau obtenus après la fusion de tab1 et tab2 
    */
    for (compteur = 0; compteur <= n; compteur++)
    {
        if (tab1[i] < tab2[j])
        {
            m1 = m2; // Stocker m2 dans m1
            m2 = tab1[i];
            i++;
        }
        else
        {
            m1 = m2; // Store the prev median
            m2 = tab2[j];
            j++;
        }
    }

    return (m1 + m2) / 2;
}

/* Fonction principale */
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));
    getchar();
    return 0;
}
                                        
def Mediane(tab1, tab2, n):
    i = 0  # indice actuel de tab1

    j = 0  # indice actuel de tab2

    m1 = -1
    m2 = -1

    # Puisqu'il y a 2n éléments,
    # la médiane sera la moyenne des éléments
    # à l'indice n-1 et n dans le tableau obtenus après la fusion de tab1 et tab2

    compteur = 0
    while compteur < n + 1:
        compteur += 1

        if tab1[i] < tab2[j]:
            m1 = m2  # Stocker m2 dans m1 (déclage)
            m2 = tab1[i]
            i += 1
        else:
            m1 = m2  # Stocker m2 dans m1 (déclage)
            m2 = tab2[j]
            j += 1

    return (m1 + m2)//2


# Tester la fonction
A = [3, 5, 7, 8, 11, 12]
B = [2, 4, 6, 9, 17, 22]
print("La médiane est ", Mediane(A, B, 6))
 La complexité de la méthode 1 est \(O(n)\)

Méthode 2 - Diviser pour régner

C’est une meilleure solution et est basée sur le paradigme Diviser pour régner. L’idée est de comparer la médiane des deux tableaux, et de résoudre récursivement le problème jusqu'à obtenir un tableau de deux éléments

Procedure : 
  1. Calculez les médianes m1 et m2 des tableaux d'entrée A [] et B [] respectivement.
  2. Si les valeurs m1 et m2 sont toutes les deux égales, alors nous avons terminé. retourner m1 (ou m2)
  3. Si m1 est supérieur à m2, alors la médiane est présente dans l'un des deux sous-réseaux ci-dessous.
    •  Du premier élément de A à m1 (A [0...n//2])
    •  Du m2 au dernier élément de B (B[n // 2 ... n-1])
  4. Si m2 est supérieur à m1, alors la médiane est présente dans l'un des deux sous-réseaux ci-dessous.
    •  De m1 au dernier élément de A (A[n / 2 ... n-1])
    •  Du premier élément de B au m2 (B[0 ... n / 2])
  5. Répétez le processus ci-dessus jusqu'à ce que la taille des deux sous-tableaux devienne 2.
  6. Si la taille des deux tableaux est de 2, utilisez la formule ci-dessous pour obtenir la médiane. $$Médiane = (max(A[0], B[0]) + min(A[1], B[1]))/2$$
Exemple : 

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;
        }

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

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

    /*
     * Médiane d'un tableau trié
     */
    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];
        }
    }

    // Fonction principale
    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;
}

/* Médiane d'un tableau */
int mediane(int tab[], int n)
{
    if (n % 2 == 0)
        return (tab[n / 2] + tab[n / 2 - 1]) / 2;
    else
        return tab[n / 2];
}

/* Fonction qui calcule la médiane de deux tableaux A, B */
int getMediane(int A[], int B[], int n)
{
    /* taille 0 */
    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); /* Médiane de A */
    int m2 = mediane(B, n); /* Médiane de B */

    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);
}

/* Fonction principale */
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));
    getchar();
    return 0;
}
                                        
def getMediane(A, B, n):

    # il n'y a aucun élément dans les deux tableaux
    if n == 0:
        return -1

    # Il n'existe qu'un seul élément dans chaque tableau
    elif n == 1:
        # Médiane est la somme des deux éléments divisée par 2
        return (A[0]+B[0])/2

    # Il existe deux éléments dans chaque tableau
    elif n == 2:
        # médiane = (max(A[0],B[0])+min(A[1],B[1]))/2
        return (max(A[0], B[0]) +
                min(A[1], B[1])) // 2

    else:
        # Calculer la médiane des deux tableaux
        m1 = mediane(A, n)
        m2 = mediane(B, n)

        if m1 > m2:
            if n % 2 == 0:  # taille pair
                # Appelez récursivement le getMediane avec les nouveaux sous-tableaux
                return getMediane(A[:n // 2 + 1],
                                  B[n // 2 - 1:], n // 2 + 1)
            else:
                # Appelez récursivement le getMediane avec les nouveaux sous-tableaux
                return getMediane(A[:n // 2 + 1],
                                  B[n // 2:], n // 2 + 1)

        else:
            if n % 2 == 0:
                # Appelez récursivement le getMediane avec les nouveaux sous-tableaux
                return getMediane(A[n//2 - 1:],
                                  B[:n//2 + 1], n // 2 + 1)
            else:
                # Appelez récursivement le getMediane avec les nouveaux sous-tableaux
                return getMediane(A[n / 2:],
                                  B[0:n // 2 + 1], n // 2 + 1)

 # Calculer la médiane d'un tableau


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


# Tester la fonction
A = [3, 5, 7, 8, 11, 12]
B = [2, 4, 6, 10, 17, 22]
print("La médiane est ", getMediane(A, B, 6))
 La complexité de la méthode 2 est \(O(logn)\)

Exercices java Exercices langage c Exercices python récursivité Tableaux Complexité analyse des algorithmes
Partager ce cours avec tes amis :
Rédigé par ESSADDOUKI Mostafa
ESSADDOUKI
The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.

Trouver un cours/exercice

Nos cours de soutien

Derniers cours

Dernières capsules vidéos