Jean-Marc Bourguet a écrit :

Je ne me souviens pas d'une fois ou ce que tu proposes aurais evite de
devoir le faire.

Tu veux faire un solveur de Boggle
(cf.  http://massiveboggle.fr/game/play).

Tu as un lexique qui fait presque 400000 mots (l'officiel du scrabble version 5) sous forme de fichier texte. Tu charges ce lexique en mémoire (pour pouvoir accéder aux mots autrement que séquentiellement).

L'algorithme de résolution du boggle est facile, c'est en fait un DFS. Tu vas être amené à répondre à ce genre de questions : comment trouver le premier mot du lexique qui commence par 'K' alors que cette lettre n'est pas un mot figurant dans le lexique en sorte que bsearch va renvoyer nul. Pourtant, bsearch aura examiné dans son algorithme (sauf bol particulier) les mots JUXTATROPICAUX (d'index 215226) et KA (d'indice 215227), c'est dommage de ne pouvoir l'utiliser. Donc, si on ne veut pas se contenter d'une recherche séquentielle (qui d'ailleurs tournera sans lenteur sur un P4) il faut se recoder une recherche dichotomique, quelle plaie !


En fait, je pourrais étendre mon propos. Ce qu'il pourrait être intéressant de coder, c'est une recherche dichotomique qui épargne d'en coder jamais une, une sorte de dichotomie générique avec une interface plus générale que celle de bsearch. Voici deux exemples où on a besoin de coder une dichotomie :

*) Résoudre une équation f(x)=0 ? Même un bsearch aménagé n'y suffirait pas.

*) On a un "tableau" de N "boules", d'abord que des boules blanches puis que des boules noires (avec au moins une boule noire). Question : trouver la position de la première boule noire. La solution naturelle est une dichotomie.