Leçons Interactives de Mathématiques et Sciences

← Informatique

Recherche dichotomique : quatre choix, seize boucles

Choisissez les quatre éléments du code : la condition de boucle, la valeur initiale de hi et les deux mises à jour. À côté, l’exécution montre chaque itération sur un petit tableau trié. Le verdict teste tous les tableaux jusqu’à la longueur fixée et toutes les valeurs cibles ; le premier cas d’échec est accessible d’un clic.

Chargement de la simulation interactive...

Leçon

La théorie — Recherche dichotomique : quatre choix, seize boucles

La recherche dichotomique trouve une valeur x dans un tableau trié en conservant un intervalle d’indices allant de lo à hi, dans lequel x doit se trouver s’il est présent. Chaque itération lit l’élément central a[mid], puis ne garde que la moitié située du côté de x. L’intervalle est fermé lorsque hi est son dernier indice (lo <= hi, avec hi initialisé à n − 1). Il est demi-ouvert lorsque hi désigne le premier indice qui n’en fait pas partie (lo < hi, avec hi initialisé à n).

Ce que signifie chaque symbole

lo, hi
les bornes de l’intervalle restant à explorer
mid
⌊(lo + hi)/2⌋, l’indice lu pendant cette itération
n
le nombre d’éléments, placés aux indices 0 à n − 1
N
la longueur maximale testée par le verdict : chaque n de 0 à N et chaque cible, soit (N + 1)² cas
Suppose
Les valeurs du tableau sont distinctes, la boucle renvoie un résultat dès que a[mid] est égal à x et, dans l’exécution comme dans le verdict, les entiers n’ont pas de borne supérieure. Le tableau des débordements abandonne cette dernière hypothèse et calcule sur 32 bits, comme Java.
Ne tient plus quand
En présence de valeurs répétées, les deux boucles correctes renvoient toujours un indice contenant x, mais pas nécessairement le premier. Pour trouver la première occurrence, comme l’exige une requête d’intervalle sur un index trié, la boucle ne doit pas s’arrêter en cas d’égalité. Elle utilise un intervalle demi-ouvert, applique hi = mid dès que a[mid] ≥ x, puis prend lo comme réponse à la fin.

Quatorze des seize boucles sont fausses, et deux éléments suffisent à le montrer 🖖

Chacun des quatre choix du code mérite l’attention d’un programmeur rigoureux, et les deux options proposées paraissent plausibles. Le tableau sous les résultats soumet les seize boucles à tous les tableaux comptant jusqu’à 12 éléments et à toutes les valeurs cibles, soit 169 cas. Deux boucles réussissent. Toutes les autres échouent sur un tableau d’au plus deux éléments ; treize des quatorze se trompent avec un seul élément ou avec le tableau vide. Limitez le test à 1 élément : trois boucles survivent. À 2, seules les deux bonnes restent. À 256, aucun premier cas d’échec n’a changé. Ces petits cas forment un test exhaustif, non un échantillon, car la boucle ne fait qu’une chose des valeurs : elle les compare à x. Tout tableau trié de n nombres distincts se comporte comme 1, 3, 5… La cible occupe l’un de ses 2n + 1 emplacements, soit sur un élément, soit dans un intervalle, et le verdict les essaie tous. Dans Programming Pearls, Jon Bentley résume la difficulté par deux dates : « La première recherche dichotomique a été publiée en 1946, mais il a fallu attendre 1962 pour voir paraître la première qui fonctionne correctement pour toute valeur de n. »

Les deux boucles presque justes ne ratent chacune qu’une cible au plus par tableau 🖖

Appuyez sur Ignore le dernier. Avec lo < hi et hi = n − 1, la boucle s’arrête lorsque lo rejoint hi, sans lire l’élément situé à cet indice. Chaque mise à jour conserve x dans l’intervalle, mais mid n’atteint jamais hi. Le seul élément qui risque de ne pas être lu est donc celui sur lequel hi commence : la boucle trouve tous les éléments de tous les tableaux, sauf le dernier. Appuyez sur Lit après la fin pour observer le défaut symétrique. Avec hi = n et lo <= hi, a[n] appartient à l’intervalle ; seule une cible supérieure à tous les éléments conduit lo jusque-là. Jusqu’à 256 éléments, ces deux boucles se trompent respectivement dans 256 et 257 des 66 049 cas. Pour le seul tableau de 256 éléments, les erreurs ne concernent que 0,19 % des valeurs cibles : cent cibles choisies au hasard passeraient généralement à côté des deux bogues. Le tableau vide suffit à prendre la seconde boucle en défaut sur son unique cas ; un tableau d’un seul élément révèle la première. En JavaScript, la seconde s’en tire même sans erreur apparente : a[n] vaut undefined, les deux comparaisons sont fausses, puis la boucle fixe hi = mid − 1 et répond −1, ce qui est exact. En Java, la même lecture déclenche une exception ; en C, son comportement est indéfini.

La boucle correcte du JDK cessait de fonctionner au-delà de 230 éléments 🖖

La boucle du JDK occupe la première ligne du tableau. Elle réussit tous les cas que le verdict peut tester, et c’est celle que Joshua Bloch a écrite pour java.util.Arrays. En Java, lo + hi est un int sur 32 bits ; au-delà de 2 147 483 647, la somme revient à une valeur négative. Un rapport de bogue déposé auprès de Sun le 11 mai 2004 décrivait la recherche du dernier élément dans un tableau de 1 100 000 000 octets, qui aboutissait à ArrayIndexOutOfBoundsException: -1064671149. Le tableau des débordements reproduit cette recherche sans rien allouer. À l’étape 6, lo + hi vaut 2 165 624 999 ; après le débordement et le décalage, le milieu devient −1 064 671 149, exactement comme dans le rapport. À la même étape, lo + ((hi − lo) >> 1) donne 1 082 812 499. Le titre du rapport indique que la recherche échoue pour les tableaux plus grands que 1<<30, et la limite est exacte : saisissez 1 073 741 824, la plus grande valeur de lo + hi est 231 − 2, qui reste représentable. Ajoutez un élément et la recherche déborde à l’étape 31. Dans son billet de 2006 consacré au bogue, Bloch écrit qu’il est resté caché « pendant environ neuf ans ». La version de Bentley dans Programming Pearls, pourtant démontrée correcte dans le livre, en souffre également. Bentley écrit que m reçoit « la moyenne de l et u, arrondie à l’entier inférieur ». C’est vrai pour les entiers mathématiques, pas pour ceux codés sur 32 bits.

Problème entièrement résolu

  1. Pourquoi seules deux boucles résistent 4 étapes

    Cliquez sur Blocage avec lo = mid. Le verdict sait tester des tableaux comptant jusqu’à 256 éléments, pas davantage. Démontrez, pour tout n, que la boucle semi-ouverte avec lo = mid + 1 se termine toujours, que la même boucle avec lo = mid se bloque dès que hi = lo + 1 et a[lo] < x, puis déduisez ce que ce raisonnement impose à la boucle fermée.

    Ouvrez ce problème dans l'outil

    1. Dans la boucle semi-ouverte, le corps ne s’exécute que lorsque lo < hi. mid, arrondi à l’entier inférieur, est alors supérieur ou égal à lo et strictement inférieur à hi.

    2. Ainsi, hi = mid diminue hi d’au moins une unité, tandis que lo = mid + 1 augmente lo d’au moins une unité. Dans les deux cas, hi − lo, initialement égal à n, baisse d’au moins une unité à chaque passage et ne peut devenir négatif : la boucle se termine en au plus n passages.

    3. Prenons maintenant lo = mid. Lorsque hi = lo + 1, mid vaut ⌊(2lo + 1)/2⌋ = lo. Si a[lo] < x, la mise à jour laisse donc lo inchangé et l’itération suivante répète exactement la précédente. Le réglage proposé atteint cette situation avec lo = 6, hi = 7, a[6] = 13 et x = 14.

    4. La boucle fermée s’exécute tant que lo <= hi ; le cas lo = hi est donc permis. On a alors mid = lo = hi : remplacer une borne par mid ne change rien. Chaque mise à jour doit franchir mid, ce qui est légitime puisque a[mid] vient d’être lu. Dans l’intervalle semi-ouvert, hi est déjà exclu. La mise à jour hi = mid écarte donc l’élément qui vient d’être lu et tous ceux qui le suivent, puisque a[mid] > x les exclut. En revanche, hi = mid − 1 écarterait aussi a[mid − 1], qui pourrait être égal à x.

    Réponse

    À chaque passage, l’intervalle doit rétrécir sans écarter d’indice susceptible de contenir x. Au départ, il doit couvrir tout le tableau. Avec lo <= hi, il faut donc hi = n − 1, hi = mid − 1 et lo = mid + 1 ; avec lo < hi, il faut hi = n, hi = mid et lo = mid + 1. Le verdict confirme ces deux versions jusqu’à 256 éléments, mais la démonstration vaut pour tout n, ce qu’aucun test ne saurait établir. En arithmétique sur 32 bits, une hypothèse supplémentaire est nécessaire : lo + hi doit être représentable. Le troisième enseignement montre ce qui arrive lorsqu’elle ne l’est pas.

Parcours

Pourquoi un algorithme est correct

Références (2)

· Vérifié sur des sources publiées. Corrections bienvenues.