Considérons un scénario courant en programmation : étant donné un tableau de nombres entiers qui est déjà trié par ordre croissant, et une valeur cible N, l'objectif est d'identifier deux éléments distincts au sein de ce tableau dont la somme est précisément égale à N. Par exemple, avec le tableau [1, 2, 4, 7, 11, 15] et une cible N = 15, la paire attendue est [4, 11].

Approche 1 : Force Brute (Boucles Imbriquées)

Une première approche, intuitive mais moins efficace, consiste à utiliser des boucles imbriquées pour examiner toutes les paires possibles d'éléments du tableau. Pour chaque élément, nous parcourons le reste du tableau afin de trouver un complément qui formerait la somme N.

La complexité temporelle de cette méthode est quadratique, soit O(n²), ce qui la rend inappropriée pour des tableaux de grande taille.

function trouverPaireNaive(tableau: number[], sommeCible: number): number[] {
    const taille = tableau.length;
    if (taille < 2) {
        return [];
    }

    for (let indexA = 0; indexA < taille - 1; indexA++) {
        const valA = tableau[indexA];
        for (let indexB = indexA + 1; indexB < taille; indexB++) {
            const valB = tableau[indexB];
            if (valA + valB === sommeCible) {
                return [valA, valB];
            }
        }
    }
    return [];
}

Approche 2 : Optimisée avec les Deux Pointeurs

Étant donné que le tableau est trié, une méthode bien plus performante est celle des "deux pointeurs". Cette technique tire parti de l'ordre des éléments pour réduire considérablement le nombre d'opérations.

Nous initialisons un pointeur gauche (ptrGauche) au début du tableau et un pointeur droit (ptrDroit) à la fin. À chaque itération, nous calculons la somme des valeurs pointées par ptrGauche et ptrDroit.

• Si cette somme est inférieure à N, cela signifie que nous devons augmenter la somme. Puisque le tableau est trié, la seule façon d'augmenetr la somme est de déplacer ptrGauche vers la droite (vers un nombre plus grand).
• Si la somme est supérieure à N, nous devons la réduire. Pour ce faire, nous déplaçons ptrDroit vers la gauche (vers un nombre plus petit).
• Si la somme est égale à N, nous avons trouvé notre paire.

Ce processus continue tant que ptrGauche est inférieur à ptrDroit. La complexité temporelle de cette approche est linéaire, soit O(n), ce qui est nettement plus efficace.

function trouverPairePointeurs(tableau: number[], sommeCible: number): number[] {
    const taille = tableau.length;
    if (taille < 2) {
        return [];
    }

    let ptrGauche = 0;
    let ptrDroit = taille - 1;

    while (ptrGauche < ptrDroit) {
        const valeurGauche = tableau[ptrGauche];
        const valeurDroite = tableau[ptrDroit];
        const sommeActuelle = valeurGauche + valeurDroite;

        if (sommeActuelle < sommeCible) {
            ptrGauche++; // Augmenter la somme
        } else if (sommeActuelle > sommeCible) {
            ptrDroit--; // Diminuer la somme
        } else {
            return [valeurGauche, valeurDroite]; // Paire trouvée
        }
    }
    return []; // Aucune paire trouvée
}

Validation par Tests Unitaires

Pour valider l'implémentation de ces alogrithmes, voici quelques scénarios de test essentiels utilisant une structure de test commune :

import { trouverPaireNaive, trouverPairePointeurs } from './somme-deux-elements'; // Assurez-vous que le chemin est correct

describe('Tests de recherche de paire avec somme cible', () => {
    it('devrait trouver la paire pour des données normales', () => {
        const serieNumerique = [1, 2, 4, 5, 7, 9, 10];
        const cible = 8;
        const resultatBruteForce = trouverPaireNaive(serieNumerique, cible);
        const resultatPointeurs = trouverPairePointeurs(serieNumerique, cible);

        expect(resultatBruteForce).toEqual([1, 7]);
        expect(resultatPointeurs).toEqual([1, 7]);
    });

    it('devrait retourner un tableau vide pour un tableau en entrée vide', () => {
        const serieNumeriqueVide: number[] = [];
        const cible = 8;
        const resultatBruteForce = trouverPaireNaive(serieNumeriqueVide, cible);
        const resultatPointeurs = trouverPairePointeurs(serieNumeriqueVide, cible);

        expect(resultatBruteForce).toEqual([]);
        expect(resultatPointeurs).toEqual([]);
    });

    it('devrait retourner un tableau vide si aucune paire n\'est trouvée', () => {
        const serieNumerique = [1, 2, 4, 5, 7, 9, 10];
        const cible = 80; // Une cible très élevée
        const resultatBruteForce = trouverPaireNaive(serieNumerique, cible);
        const resultatPointeurs = trouverPairePointeurs(serieNumerique, cible);

        expect(resultatBruteForce).toEqual([]);
        expect(resultatPointeurs).toEqual([]);
    });
});

Comparaison des Performances

Pour illustrer la différence de perfomrance entre ces deux approches, considérons un test de charge simple mesurant le temps d'exécution pour un grand nombre d'appels :

// Mesure de performance
let monTableauTest = [1,2,3,4,5,6,7,8,9,10]; // Un tableau de taille modeste
const valeurCibleTest = 15; // Une cible qui ne sera pas trouvée, forçant la vérification complète

console.time('Performance Naive');
for (let i = 0; i < 100 * 10000; i++) {
    trouverPaireNaive(monTableauTest, valeurCibleTest);
}
console.timeEnd('Performance Naive');

console.time('Performance Pointeurs Doubles');
for (let i = 0; i < 100 * 10000; i++) {
    trouverPairePointeurs(monTableauTest, valeurCibleTest);
}
console.timeEnd('Performance Pointeurs Doubles');