Rechercher et dédupliquer

Objectifs

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

• implémenter une recherche linéaire avec sortie anticipée et convention -1 ;
• écrire un test de présence sans copier includes ;
• construire un tableau sans doublons en conservant l'ordre ;
• estimer le coût caché des solutions naïves avant la leçon sur la complexité.

🔗 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é : aucune astuce possible, il faut potentiellement tout parcourir — d'où le nom « linéaire ».

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 méritent qu'on s'y arrête :

La sortie anticipée. Dès que la cible est trouvée, return interrompt boucle et fonction. Continuer à chercher après avoir trouvé serait du travail purement perdu. Comparez les deux destins sur une liste de 10 000 éléments dont la cible est en position 2 : deux comparaisons contre dix mille.

La convention -1. Pourquoi -1 et pas null ou false pour signaler l'absence ? Parce que -1 est un index impossible : il ne peut pas être confondu avec « trouvé en première position » (0). C'est le contrat historique des outils Unix (grep) puis de JavaScript (indexOf). Vous venez de réimplémenter indexOf — vérifiez :

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

Coût selon la situation, à retenir pour plus tard :

Cible	Comparaisons effectuées
en première position	1
au milieu	n/2
absente	n (toutes !)

Le pire cas est donc « absent » : c'est lui qui définit le coût maximal de l'algorithme.

Test de présence : même algorithme, autre contrat

Si seule l'existence intéresse (pas la position), l'algorithme s'adapte en retournant un booléen :

function contient(valeurs, cible) {
  for (const v of valeurs) {
    if (v === cible) {
      return true;       // sortie anticipée dès la première égalité
    }
  }
  return false;          // boucle terminée sans trouver
}

Version courte avec les outils natifs (à savoir lire, et à préférer dans le vrai code) :

valeurs.includes(cible);

Remarquez que contient et position partagent le même squelette ; seul le type de réponse change. Savoir reconnaître cette parenté évite d'apprendre « mille algorithmes » là où il y a un motif.

Supprimer les doublons

Objectif : ["a", "b", "a", "c"] → ["a", "b", "c"], ordre conservé.

L'idée : parcourir l'entrée et ne garder chaque valeur que si elle n'a jamais été vue. Le tableau résultat sert alors à double titre : accumulation ET mémoire de ce qui existe déjà.

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

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

Tracez-le mentalement :

voir "a" : resultat [] ne contient pas "a" → push → ["a"]
voir "b" : pas vu → push                   → ["a", "b"]
voir "a" : DÉJÀ présent → refusé           → ["a", "b"]
voir "c" : pas vu → push                   → ["a", "b", "c"]

Propriétés de cette version, toutes voulues :

• l'ordre de première apparition est conservé ;
• l'entrée n'est jamais modifiée (on retourne un nouveau tableau — style puriste du chapitre 4) ;
• tableau vide → tableau vide, sans ligne de code supplémentaire.

Aperçu de la version native, pour plus tard dans le cursus :

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

Attention au coût caché

Relisez la ligne clé : resultat.includes(v). Elle parcourt resultat à chaque itération de la boucle principale. Une boucle dans une boucle — le signal d'alerte annoncé au chapitre précédent.

Concrétisons : dédoublonner 1 000 valeurs très variées demande environ

1 + 2 + 3 + ... + ~1000 ≈ 500 000 comparaisons

car au i-ème tour, resultat contient environ i éléments à vérifier. Sur dix mille éléments : ~50 millions. Invisible sur une petite liste, rédhibitoire sur un flux réel.

Deux réflexes corrects face à cela :

1. Ne pas paniquer prématurément : sur vos listes de quelques dizaines d'éléments, la version claire ci-dessus est parfaite ;
2. Savoir repérer le risque : « boucle imbriquée » doit désormais déclencher une question (« quelle taille réelle ? ») — et la prochaine leçon vous donnera le vocabulaire exact pour raisonner dessus.

Composer plutôt que dupliquer

Combinons deux algorithmes déjà écrits :

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

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

Une ligne, zéro nouvelle logique : composer des fonctions simples reste toujours préférable à écrire un monolithe — même philosophie qu'à l'ouverture du chapitre.

Exercice

1. position(valeurs, cible) — refaites-la sans regarder, testez avec cible en tête, au milieu, absente.
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.
6. Question de réflexion : pourquoi dernierePosition ne peut-elle pas profiter d'une sortie anticipée vers l'avant comme position ?

Résumé

• Recherche linéaire : parcours + comparaison + sortie anticipée ; absence notée -1 (index impossible).
• Test de présence : même squelette, contrat booléen.
• Dédoublonnage : accumulateur qui sert aussi de mémoire (includes sur soi-même).
• Boucles imbriquées = coût quadratique latent : à repérer tôt, optimiser seulement si la taille réelle l'exige.

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;
}
// Variante élégante : parcourir depuis la fin et sortir anticipément,
// mais elle exige une boucle décroissante — la version mémorisante reste la plus simple.

function sansDoublonsNombres(nombres) {
  const resultat = [];
  for (const n of nombres) {
    if (!resultat.includes(n)) {
      resultat.push(n);
    }
  }
  return resultat;
}
// Trace [2, 1, 2] : 2 ajouté → 1 ajouté → 2 refusé (déjà présent)
//                 → [2, 1] : l'ordre de première apparition est conservé ✓

function tousUniques(valeurs) {
  return sansDoublons(valeurs).length === valeurs.length;
}
// Composition pure : si le dédoublonnage retire quelque chose, ce quelque chose était un doublon.
// Coût identique au dédoublonnage complet — mais code trois fois plus court.

function premierDoublon(valeurs) {
  const vus = [];
  for (const v of valeurs) {
    if (vus.includes(v)) {
      return v;          // première valeur DÉJÀ rencontrée : c'est notre doublon
    }
    vus.push(v);
  }
  return null;
}
// Trace ["a","b","a"] :
//   "a" : vus=[] ne le contient pas → vus=["a"]
//   "b" : pas vu                    → vus=["a","b"]
//   "a" : DÉJÀ dans vus             → return "a"