Explication du code

Avant de plonger dans le code, commençons par un résumé. Ce code résout un problème difficile: trouver la médiane (la valeur du milieu) quand nous avons deux listes de nombres déjà triés. C'est un problème classique d'algorithmique qui utilise la technique de recherche binaire pour obtenir une solution efficace.

La médiane et son importance

La médiane est un concept mathématique qui représente la valeur du milieu d'un ensemble de nombres. Si nous avons une liste de nombres triés, la médiane est facile à trouver: c'est l'élément du milieu pour un nombre impair d'éléments, ou la moyenne des deux éléments du milieu pour un nombre pair d'éléments.

Trouver la médiane de deux listes séparées est plus complexe. Une approche naïve serait de fusionner les deux listes en une seule liste triée, puis de trouver la médiane, mais cela nécessiterait beaucoup de temps et d'espace. Le code utilise une méthode plus intelligente appelée recherche binaire.

La recherche binaire: un jeu de "Plus petit, plus grand"

La recherche binaire est comme le jeu où tu dois deviner un nombre entre 1 et 100, et à chaque essai, on te dit "plus petit" ou "plus grand". Cette technique est particulièrement efficace car elle divise l'espace de recherche en deux à chaque étape, réduisant considérablement le nombre d'opérations nécessaires.

Exemple simple

Imagine que tu cherches un mot dans un dictionnaire. Tu ne vas pas lire chaque page une par une ! Tu ouvres le dictionnaire au milieu, tu regardes si le mot que tu cherches est avant ou après, puis tu continues à "couper" les pages en deux jusqu'à trouver ton mot.

Analyse du code pas à pas

Préparation des tableaux

if (first.length > second.length) {
    [first, second] = [second, first];
}

Cette première partie s'assure que nous travaillons avec le plus petit tableau pour notre recherche binaire. C'est comme si tu avais deux piles de livres et que tu choisissais la plus petite pile pour chercher, car c'est plus rapide.

Calcul des indices importants

const total = first.length + second.length;
const middle = Math.floor((total + 1) / 2);

Nous calculons le nombre total d'éléments et déterminons où se trouve le milieu. C'est comme mesurer la taille totale de nos deux piles de livres et déterminer où se trouverait le livre du milieu si nous les mettions tous en une seule pile.

La recherche binaire en action

let left = 0;
let right = first.length;

while (left <= right) {
    // Calcul des partitions :
    const half = Math.floor((left + right) / 2);
    const partitions = {
        left: half,
        right: middle - half
    };

Ici commence notre recherche binaire. Nous essayons de diviser nos deux tableaux en "partitions gauche" et "partitions droite" de façon à ce que tous les éléments à gauche soient plus petits que tous les éléments à droite.

Vérifier si notre partition est correcte

// Déterminer les valeurs maximales du côté gauche :
const max = {
    left: (partitions.left === 0) ? -Infinity : first[partitions.left - 1],
    right: (partitions.right === 0) ? -Infinity : second[partitions.right - 1]
};

// Déterminer les valeurs minimales du côté droit :
const min = {
    left: (partitions.left === first.length) ? Infinity : first[partitions.left],
    right: (partitions.right === second.length) ? Infinity : second[partitions.right]
};

Nous vérifions les valeurs à la frontière de nos partitions. Si notre partition est correcte, le plus grand élément à gauche doit être plus petit que le plus petit élément à droite.

Calcul de la médiane

if (max.left <= min.right && max.right <= min.left) {
    if (total % 2 === 0) {
        return (Math.max(max.left, max.right) + Math.min(min.left, min.right)) / 2;
    } else {
        return Math.max(max.left, max.right);
    }
}

Une fois que nous avons trouvé la bonne partition, nous calculons la médiane. Si le nombre total d'éléments est pair, nous prenons la moyenne des deux éléments du milieu. Sinon, nous prenons le plus grand élément à gauche.

Ajustement de la recherche

if (max.left > min.right) {
    right = partitions.left - 1;
} else {
    left = partitions.left + 1;
}

Si notre partition n'est pas correcte, nous ajustons notre recherche binaire. C'est comme tourner les pages d'un livre: si le mot que tu cherches est après la page actuelle, tu vas plus loin; s'il est avant, tu recules.

L'élégance de l'algorithme

Ce qui rend ce code spécial, c'est son efficacité. Au lieu de trier et fusionner deux tableaux (ce qui serait lent), il utilise une recherche binaire pour trouver directement la médiane. C'est comme trouver un trésor en suivant une carte plutôt que de creuser tout le terrain.

Pour chaque étape de la recherche binaire, nous divisons notre espace de recherche par deux, ce qui nous donne une complexité temporelle de O(log(min(n, m))) où n et m sont les tailles des deux tableaux.

Cette approche élégante nous montre comment une bonne compréhension des algorithmes peut transformer un problème difficile en une solution élégante et efficace.