Chercher : recherche linéaire et recherche dichotomique

Pour trouver un nom dans une liste triée d'un million de noms, la recherche dichotomique n'a jamais besoin de plus de 20 vérifications.

Chercher une valeur

La recherche consiste à trouver où se trouve une valeur dans une collection, ou à apprendre qu'elle n'y est pas. Ton téléphone le fait quand tu tapes le nom d'un contact, une boutique le fait quand elle vérifie si un article est en stock, et un correcteur orthographique le fait pour chaque mot que tu tapes. L'entrée est une liste et une valeur cible. La sortie est la position de la cible, ou un signe comme -1 qui veut dire « introuvable ».

La recherche linéaire : une valeur à la fois

La méthode la plus simple consiste à partir de la gauche et à vérifier chaque valeur à tour de rôle jusqu'à trouver la cible ou arriver au bout de la liste. C'est la recherche linéaire (ou séquentielle). Elle fonctionne sur n'importe quelle liste, triée ou non. Son coût dépend de la chance : si la cible est en premier, une vérification suffit ; si elle est en dernier ou absente, on vérifie toutes les valeurs. Pour une liste de n valeurs, le pire cas est n vérifications. Une liste deux fois plus longue peut demander deux fois plus de vérifications, d'où le nom « linéaire » : le travail augmente en ligne droite avec la taille.

function linearSearch(list, target) {
  for (let i = 0; i < list.length; i++) {
    if (list[i] === target) return i;  // trouvée
  }
  return -1;                             // tout a été vérifié
}

La recherche dichotomique : couper en deux ce qui reste

Si la liste est triée, on peut faire bien mieux. Pense au jeu du nombre à deviner : quelqu'un choisit un nombre de 1 à 100 et ne répond que « plus grand » ou « plus petit ». Un joueur malin propose d'abord 50. Quelle que soit la réponse, la moitié des possibilités disparaît. La proposition suivante est le milieu de ce qui reste, et ainsi de suite. La recherche dichotomique (ou binaire) fait exactement cela avec une liste triée. Elle garde deux repères, lo et hi, autour de la partie où la cible pourrait encore se trouver. Elle vérifie la valeur du milieu. Si c'est la cible, c'est fini. Si la valeur du milieu est plus petite que la cible, tout ce qui est à sa gauche est plus petit aussi : lo passe donc après le milieu. Si elle est plus grande, hi passe avant le milieu. Quand lo dépasse hi, il ne reste rien et la cible n'est pas dans la liste.

function binarySearch(list, target) {
  let lo = 0, hi = list.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (list[mid] === target) return mid;
    if (list[mid] < target) lo = mid + 1;  // la cible est à droite
    else hi = mid - 1;                     // la cible est à gauche
  }
  return -1;
}

Combien de vérifications ?

Chaque vérification de la recherche dichotomique divise au moins par deux la partie restante. En partant de n valeurs, il en reste au plus environ n/2 après une vérification, environ n/4 après deux, et ainsi de suite jusqu'à ce qu'il ne reste qu'une valeur. Le nombre de divisions par deux nécessaires pour passer de n à 1 est le logarithme de base 2 de n, noté log₂ n. En comptant aussi la dernière vérification, la recherche dichotomique demande au plus ⌊log₂ n⌋ + 1 vérifications, où ⌊ ⌋ signifie arrondir à l'entier inférieur. Pour 100 valeurs, cela fait 7 vérifications : c'est pourquoi on peut toujours gagner au jeu du nombre à deviner en 7 propositions. Pour 1000 valeurs, c'est 10, pour un million 20, et pour un milliard 30.

Le piège : la liste doit être triée

La recherche dichotomique ne fonctionne que parce que, dans une liste triée, une seule comparaison indique de quel côté doit se trouver la cible. Dans une liste non triée, la valeur du milieu n'apprend rien sur ses voisines : on revient donc à la recherche linéaire. Trier demande aussi du travail (les deux unités suivantes en parlent) : le choix dépend donc de l'usage. Si tu cherches une seule fois dans une liste, une recherche linéaire est peut-être la moins coûteuse. Si tu cherches des milliers de fois dans la même liste, la trier une fois puis utiliser la recherche dichotomique devient vite rentable. Ce compromis entre la préparation des données et les réponses aux questions qu'on leur pose traverse toute la discipline.