La recherche binaire est plus difficile à mettre en œuvre qu'il n'y paraît. "Bien que l'idée de base de la recherche binaire soit relativement simple, les détails peuvent être étonnamment délicats " - Donald Knuth.
Quels bogues sont les plus susceptibles d'être introduits dans une nouvelle implémentation de la recherche binaire ?
Cette question a été Je viens de poser à nouveau la question récemment . En dehors de la citation de Knuth selon laquelle "Bien que l'idée de base de la recherche binaire soit relativement simple, les détails peuvent être étonnamment délicats", il y a le fait historique stupéfiant (voir TAOCP, Volume 3, section 6.2.1) que la recherche binaire a été publiée pour la première fois en 1946 mais que la première recherche binaire publiée sans bugs était en 1962. Et il y a l'expérience de Bentley qui, lorsqu'il a assigné la recherche binaire dans les cours pour les programmeurs professionnels dans des endroits comme Bell Labs et IBM et leur a donné deux heures, tout le monde a rapporté qu'ils avaient eu raison, et en examinant leur code, 90% d'entre eux avaient des bogues - année après année.
La raison fondamentale pour laquelle tant de programmeurs font des erreurs avec la recherche binaire, outre la loi de Sturgeon, est peut-être qu'ils ne sont pas assez prudents : Perles de la programmation cite cette approche comme étant l'approche "écrivez votre code, jetez-le par-dessus le mur et laissez l'assurance qualité ou les tests s'occuper des bogues". Et il y a beaucoup de possibilités d'erreurs. Pas seulement l'erreur de débordement que plusieurs autres réponses mentionnent ici, mais aussi les erreurs logiques.
Vous trouverez ci-dessous quelques exemples d'erreurs de recherche binaire. Cette liste n'est en aucun cas exhaustive. (Comme l'écrit Tolstoï dans Anna Karénine - "Toutes les familles heureuses se ressemblent ; chaque famille malheureuse est malheureuse à sa manière" - chaque programme de recherche binaire incorrect est incorrect à sa manière).
Le code Pascal suivant est extrait du document Erreurs de manuels dans la recherche binaire (1988) par Richard E Pattis. Il a examiné vingt manuels et a trouvé cette recherche binaire (BTW, Pascal utilise des index de tableau commençant par 1) :
PROCEDURE BinarySearch (A : anArray,
Size : anArraySize,
Key : INTEGER,
VAR Found : BOOLEAN;
VAR Index : anArrayIndex);
Var Low, High : anArrayIndex;
BEGIN
LOW := 1;
High := Size;
REPEAT
Index := (Low + High) DIV 2;
If Key < A[Index]
THEN High := Index - 1
ELSE Low := Index + 1
UNTIL (Low > High) OR (Key = A[Index]);
FOUND := (Low <= High)
END;Ça a l'air bien ? Il y a plus d'une erreur. Avant de poursuivre votre lecture, essayez de les trouver toutes. Vous devriez être capable de deviner ce que fait le code, même si vous voyez Pascal pour la première fois.
Il décrit cinq erreurs que présentent de nombreux programmes, et en particulier le programme ci-dessus :
Erreur 1 : Il ne s'exécute pas en temps O(log n), où n = Taille. Dans leur enthousiasme pour les bonnes pratiques de programmation, certains programmeurs écrivent la recherche binaire comme une fonction/procédure, et lui passent un tableau. (Ceci n'est pas spécifique à Pascal ; imaginez en C++ passer un vecteur par valeur plutôt que par référence). Cela représente Θ(n) de temps juste pour passer le tableau à la procédure, ce qui va à l'encontre de tout l'objectif. Pire encore, certains auteurs donnent apparemment une récursif recherche binaire, qui passe un tableau à chaque fois, ce qui donne un temps d'exécution qui est Θ(n log n). (Ce n'est pas farfelu ; j'ai effectivement vu du code de ce type).
Erreur 2 : Il échoue lorsque la taille = 0. Cela peut être correct. Mais selon l'application prévue, la liste/table à rechercher mai rétrécit à 0, et il doit être traité quelque part.
Erreur 3 : Il donne une mauvaise réponse. Chaque fois que l'itération finale de la boucle commence avec Low=High (par exemple lorsque Size=1), elle met Found:=True, même si Key n'est pas dans le tableau.
Erreur 4 : Il provoque une erreur chaque fois que Key est inférieur au plus petit élément du tableau. (Après Index devient 1, il fixe High à 0, etc. ; provoque une erreur hors limites).
Erreur 5 : Il provoque une erreur chaque fois que Key est supérieur au plus grand élément du tableau. (Après Index devient Size il fixe Low à Size+1 etc. ; provoque une erreur hors limites).
Il souligne également que certaines façons évidentes de "corriger" ces erreurs s'avèrent également erronées. Le code de la vie réelle a aussi souvent cette propriété, lorsqu'un programmeur a écrit quelque chose d'incorrect, a trouvé une erreur, puis l'a "corrigée" jusqu'à ce qu'elle soit semblait correctes sans y réfléchir suffisamment.
Sur les 20 manuels qu'il a essayés, seuls 5 présentaient une recherche binaire correcte. Dans les 15 autres (il dit 16, ironiquement), il a trouvé 11 cas d'erreur 1, six cas d'erreur 2, deux cas d'erreur 3 et 4 et un cas d'erreur 5. Le total de ces chiffres est bien supérieur à 15, car plusieurs d'entre eux comportaient plusieurs erreurs.
La recherche binaire ne sert pas seulement à rechercher un tableau pour voir s'il contient une valeur, voici donc un autre exemple pour le moment. Il se peut que je mette à jour cette liste si j'en trouve d'autres.
Supposons que vous ayez une fonction f croissante (non décroissante) : R->R, et (parce que vous voulez une Racine de f, disons), vous voulez trouver la plus grande t de telle sorte que f(t) < 0 . Voyez combien de bogues vous pouvez trouver dans ce qui suit :
float high = INF, low = 0;
while(high != low) {
float mid = (low + high)/2;
if(f(mid)>0) high=mid;
else low=mid;
}
printf("%f", high);(Certains : Il se peut qu'il n'y ait pas de tel t dans [0,INF], si f est 0 sur un intervalle alors c'est faux, ne jamais comparer des nombres à virgule flottante pour l'égalité, etc.)
J'avais l'habitude de faire plusieurs de ces erreurs - les quelques premières douzaines de fois où j'ai écrit une recherche binaire (c'était lors de concours de programmation où le temps était compté), environ 30% du temps il y avait un bug quelque part - jusqu'à ce que je trouve la manière simple de l'écrire correctement. Depuis, je ne me suis plus trompé dans une recherche binaire (si je me souviens bien). L'astuce est très simple :
Maintenir un invariant.
Trouvez/décidez et rendez explicite une propriété invariante que vos variables "basse" et "haute" satisfont tout au long de la boucle : avant, pendant et après. Assurez-vous qu'elle n'est jamais violée. Bien entendu, vous devez également penser à la condition de terminaison. Ce point est expliqué en détail dans le chapitre 4 de l'ouvrage Perles de la programmation dont dérive un programme de recherche binaire à partir de méthodes semi-formelles.
Par exemple, pour rendre légèrement abstraite la condition examinée, supposons que l'on veuille trouver la plus grande valeur entière x pour laquelle une certaine condition poss(x) est vrai. Même cette définition explicite du problème est plus que ce que beaucoup de programmeurs ont au départ. (Par exemple, poss(x) peut être a[x] ≤ v pour une certaine valeur v ; il s'agit de trouver combien d'éléments dans le tableau trié a sont plus grands que v , disons). Alors, une façon d'écrire la recherche binaire est :
int lo=0, hi=n;
//INVARIANT: poss(lo) is true, poss(hi) is false
//Check and ensure invariant before starting binary search
assert(poss(lo)==true);
assert(poss(hi)==false);
while(hi-lo>1) {
int mid = lo + (hi-lo)/2;
if(poss(mid)) lo = mid;
else hi = mid;
}
printf("%d \n",lo);Vous pouvez ajouter d'autres déclarations d'assertion et d'autres vérifications, mais l'idée de base est que, parce que vous mettez à jour le fichier lo à mid uniquement quand vous savez que poss(mid) est vrai, vous maintenez l'invariant que poss(lo) est toujours vrai. De même, vous définissez hi à mid seulement quand poss(mid) est faux, donc vous maintenez l'invariant que poss(hi) est toujours fausse. Pensez à la condition de terminaison séparément. (Notez que lorsque hi-lo est de 1, mid est la même chose que lo . Donc n'écrivez pas la boucle comme while(hi>lo) ou vous aurez une boucle infinie). A la fin de la boucle, vous avez la garantie que hi-lo est au plus égal à 1, et parce que vous avez toujours maintenu votre invariant ( poss(lo) est vrai et poss(hi) est fausse), elle ne peut pas être 0. De plus, toujours grâce à votre invariant, vous savez que lo est la valeur à retourner/imprimer/utiliser. Il existe bien sûr d'autres façons d'écrire une recherche binaire, mais le maintien d'un invariant est une astuce/discipline qui aide toujours.
En voici quelques-unes qui me viennent à l'esprit :
Est-ce que c'est ce que vous avez à l'esprit ?
Lire la suite . L'implémentation de la recherche binaire de Java a caché un bogue pendant près de dix ans avant que quelqu'un ne le trouve.
Le bogue est un dépassement d'entier. Il n'a pas causé de problèmes aux gens parce que presque personne ne cherchait des structures de données assez grandes.
Si vous avez le livre Programming Pearls à proximité, vous devriez consulter le chapitre 4.
edit2 : Comme indiqué dans les commentaires, vous pouvez télécharger le projet de chapitre que j'ai mentionné sur le site de l'auteur : http://www.cs.bell-labs.com/cm/cs/pearls/sketch04.html
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
