01 — La recherche dichotomique et ses pièges

Ce que tu vas apprendre

• Le principe de la recherche dichotomique et pourquoi elle est en O(log n)
• Une implémentation correcte en TypeScript et Python
• Le piège du calcul du milieu (débordement)
• Les erreurs de bornes qui causent des boucles infinies

Prérequis

• 00 — Introduction

La recherche dichotomique est l'un des algorithmes les plus simples à décrire et les plus difficiles à écrire correctement. Donald Knuth a fait remarquer que, bien que le premier article décrivant l'idée date de 1946, la première version sans bug n'a été publiée qu'en 1962. Le concept tient en une phrase ; les détails de bornes font trébucher tout le monde. On va voir l'idée, puis les pièges précis.

Le principe

La condition d'usage : le tableau doit être trié. On cherche une cible en regardant l'élément du milieu. Trois cas :

• l'élément du milieu est la cible : trouvé ;
• la cible est plus petite : elle ne peut être que dans la moitié gauche, on ignore la droite ;
• la cible est plus grande : elle ne peut être que dans la moitié droite, on ignore la gauche.

À chaque étape, on élimine la moitié des éléments restants. C'est ce qui donne le O(log n) : sur un million d'éléments, au plus 20 étapes, contre un million pour un parcours linéaire.

typescriptfunction rechercheDichotomique(arr: number[], cible: number): number {
  let bas = 0;
  let haut = arr.length - 1;
  while (bas <= haut) {
    const milieu = bas + Math.floor((haut - bas) / 2);
    if (arr[milieu] === cible) return milieu;
    if (arr[milieu] < cible) bas = milieu + 1;
    else haut = milieu - 1;
  }
  return -1; // absent
}

pythondef recherche_dichotomique(arr: list[int], cible: int) -> int:
    bas, haut = 0, len(arr) - 1
    while bas <= haut:
        milieu = bas + (haut - bas) // 2
        if arr[milieu] == cible:
            return milieu
        if arr[milieu] < cible:
            bas = milieu + 1
        else:
            haut = milieu - 1
    return -1

Piège 1 : le calcul du milieu

Le calcul du milieu paraît anodin. La version intuitive est (bas + haut) / 2. Elle contient un bug célèbre, présent pendant des années dans la bibliothèque standard de Java et dans le livre Programming Pearls. Quand bas et haut sont de grands entiers, leur somme peut dépasser la valeur maximale d'un entier signé et déborder, donnant un index négatif.

La parade est d'écrire bas + (haut - bas) / 2. La soustraction haut - bas ne déborde jamais (elle est plus petite que haut), et on rajoute l'offset. En JavaScript, les nombres sont des flottants 64 bits, donc le débordement d'entiers n'arrive pas dans les mêmes conditions, mais l'habitude reste saine et indispensable dans les langages à entiers bornés (Java, C, Rust, Go).

Piège 2 : les bornes et la boucle infinie

La deuxième source de bugs, c'est la gestion des bornes : < ou <= dans la condition, milieu ou milieu ± 1 dans les mises à jour. Une incohérence et tu obtiens soit une boucle infinie, soit un élément jamais testé.

La règle qui marche : si tu utilises while (bas <= haut) avec haut initialisé à length - 1 (intervalle fermé des deux côtés), alors les mises à jour doivent exclure le milieu déjà testé, donc bas = milieu + 1 et haut = milieu - 1. Si tu oublies le + 1 ou le - 1, l'intervalle ne rétrécit plus quand la cible n'est pas trouvée, et la boucle tourne sans fin.

Le test mental qui sauve : vérifie que l'intervalle [bas, haut] rétrécit strictement à chaque tour. Si dans un cas il peut rester identique, tu as une boucle infinie en germe.

Ne pas réimplémenter sans raison

En pratique, les langages fournissent souvent la recherche dichotomique. Python a le module bisect (bisect_left, bisect_right). Beaucoup d'écosystèmes ont un équivalent. JavaScript n'a pas de recherche binaire native sur les tableaux, mais des bibliothèques l'offrent. Réimplémenter à la main est justifié quand tu as besoin d'une variante (chercher une frontière plutôt qu'une valeur exacte, ce qu'on verra à l'article suivant), ou pour comprendre. Pour une recherche exacte basique, utilise l'outil du langage : il est testé contre les pièges ci-dessus.

Note le compromis : la dichotomie demande un tableau trié (le tri coûte O(n log n) une fois). Si tu cherches souvent sans avoir besoin d'ordre, un Set en O(1) est meilleur. La dichotomie brille quand les données sont déjà triées, ou quand tu as besoin de l'ordre pour autre chose (frontières, plages).

L'article suivant montre que la dichotomie va bien au-delà de « trouver une valeur exacte » : trouver une frontière, ou même chercher la réponse à un problème d'optimisation.

Sources

• Bentley, J. (2000). Programming Pearls (2nd ed.), Colonne 4 "Writing Correct Programs". Addison-Wesley.
• Bloch, J. (2006). Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken. Google Research Blog. (Le bug du milieu dans la stdlib Java)
• Knuth, D. E. (1998). The Art of Computer Programming, Vol. 3, Section 6.2.1. Addison-Wesley.
• Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Exercice 2.3-5. MIT Press.