Rechercher et dédupliquer

Objectifs

À la fin de cette leçon, vous saurez :

• implémenter une recherche linéaire avec sortie anticipée ;
• écrire un test de présence sans copier includes ;
• construire un tableau sans doublons ;
• comprendre le coût caché des solutions naïves.

🔗 Pour vous rafraîchir la mémoire : parcourir, sommer, compter

La recherche linéaire

Trouver la position d'une valeur dans un tableau non trié : il faut potentiellement tout parcourir.

function position(valeurs, cible) {
  for (let i = 0; i < valeurs.length; i++) {
    if (valeurs[i] === cible) {
      return i;          // trouvé : on sort immédiatement
    }
  }
  return -1;             // convention : -1 signifie « absent »
}

console.log(position([7, 3, 9], 3));    // 1
console.log(position([7, 3, 9], 4));    // -1

Deux choix à remarquer :

• Sortie anticipée : dès que la cible est trouvée, return interrompt tout. Continuer serait du travail perdu.
• Convention -1 : l'absence est signalée par une valeur impossible comme index. C'est le contrat de la méthode native indexOf — vous venez de la réimplémenter.

Test de présence

Si seule l'existence intéresse :

function contient(valeurs, cible) {
  for (const v of valeurs) {
    if (v === cible) {
      return true;
    }
  }
  return false;
}

Version courte avec les outils natifs (à savoir lire) :

valeurs.includes(cible);

Supprimer les doublons

Objectif : ["a", "b", "a", "c"] → ["a", "b", "c"].

Algorithme de base : parcourir, et ne garder chaque valeur que si elle n'a pas encore été vue.

function sansDoublons(valeurs) {
  const resultat = [];
  for (const v of valeurs) {
    if (!resultat.includes(v)) {   // pas encore rencontrée ?
      resultat.push(v);
    }
  }
  return resultat;
}

console.log(sansDoublons(["a", "b", "a", "c"]));   // ["a", "b", "c"]

Propriétés de cette version :

• l'ordre d'apparition est conservé ;
• l'entrée n'est jamais modifiée (on retourne un nouveau tableau) ;
• tableau vide → tableau vide, sans cas particulier à écrire.

Aperçu de la version bibliothèque, pour plus tard dans le cursus :

[...new Set(valeurs)]   // Set ne stocke jamais deux valeurs identiques

Attention au coût

resultat.includes(v) parcourt resultat à chaque itération. Sur une petite liste, invisible. Sur dix mille éléments très dupliqués, le travail devient quadratique (voir la leçon sur la complexité qui suit). Retenez le réflexe :

boucle dans une boucle = signal d'alerte sur la performance

Pas de panique pour autant : la clarté d'abord, l'optimisation seulement quand une taille réelle pose problème.

Compter les valeurs distinctes

Combinons deux algorithmes déjà écrits :

function nombreValeursDistinctes(valeurs) {
  return sansDoublons(valeurs).length;
}

console.log(nombreValeursDistinctes([1, 2, 2, 3, 3, 3]));   // 3

Composer des fonctions simples plutôt qu'écrire un monolithe : même philosophie que pour les problèmes.

Exercice

1. position(valeurs, cible) — refaites-la sans regarder.
2. dernierePosition(valeurs, cible) — index de la dernière occurrence, -1 si absente.
3. sansDoublonsNombres(nombres) — dédoublonnage ; vérifiez que [2, 1, 2] renvoie bien [2, 1] (ordre conservé).
4. tousUniques(valeurs) — vrai si aucune valeur n'apparaît deux fois. Indice : comparez les longueurs avant/après dédoublonnage.
5. premierDoublon(valeurs) — renvoie la première valeur vue en double, ou null.

Résumé

• Recherche linéaire : parcours + comparaison + sortie anticipée ; absence notée -1.
• Dédoublonnage par accumulation avec test d'adhésion (includes).
• Boucles imbriquées : correctes mais coûteuses — à connaître avant d'optimiser.

function dernierePosition(valeurs, cible) {
  let trouvee = -1;
  for (let i = 0; i < valeurs.length; i++) {
    if (valeurs[i] === cible) {
      trouvee = i;      // on note, mais on ne s'arrête pas :
                        // une occurrence ultérieure peut exister
    }
  }
  return trouvee;
}

function sansDoublonsNombres(nombres) {
  const resultat = [];
  for (const n of nombres) {
    if (!resultat.includes(n)) {
      resultat.push(n);
    }
  }
  return resultat;
}
// [2, 1, 2] : 2 ajouté, 1 ajouté, 2 refusé → [2, 1]

function tousUniques(valeurs) {
  return sansDoublons(valeurs).length === valeurs.length;
}

function premierDoublon(valeurs) {
  const vus = [];
  for (const v of valeurs) {
    if (vus.includes(v)) {
      return v;          // première valeur déjà rencontrée
    }
    vus.push(v);
  }
  return null;
}