"Charlie Gordon" <news@chqrlie.org> writes:

Primo, la recherche dichotomique dans un tableau en mémoire n'est pas une
plaie à coder, tout au plus un rapide échauffement des petits doigts pour
le petit déjeuner.  Une implementation simple et de bon gout fait à peine
un vingtaine de lignes:

void *bsearch(const void *key, const void *base, size_t nmemb, size_t size,
              int (*compar)(const void *, const void *))
{
    size_t a = 0;
    size_t b = nmemb;

    while (a < b) {
        size_t m = (a + b) / 2;
        const void *p = (const char *)base + m * size;
        int cmp = (*compar)(key, p);
        if (cmp < 0)
            b = m;
        else
        if (cmp > 0)
            a = m + 1;
        else
            return (void *)p;
    }
    return NULL;
}

Il ne faut pas coder avant le petit dejeuner :-) La preuve, tu nous a fait
une belle boucle infinie.  (Et je ne vois pas l'utilite du +1 dans a = m
+1).

On peut dans ce cas améliorer légèrement l'efficacité de la recherche et
garantir de trouver le premier match en cas de doublons en remplacant les
deux tests sur cmp par un seul (laissé au lecteur à titre d'exercice ;-).

Rien n'empeche de faire cela ici aussi, il suffit de tester l'egalite avant
de retourner une valeur.  C'est un gain meme si la valeur se trouve
toujours dans le tableau.

Troisièmement, la recherche dichotomique n'est pas le meilleur algorithme
pour le probleme posé (boggle solver). Il sera bien plus efficace de
stocker tous les mots possibles dans un tableau associatif (hash table)
convenablement dimensionné et avec une API de recherche efficace.

Il a l'air d'avoir besoin de prefixes (j'ai toujours pas ete voir le jeu),
auquel cas une hash table n'est pas particulierement adaptee.

A+

--
Jean-Marc
FAQ de fclc:       http://www.isty-info.uvsq.fr/~rumeau/fclc
Site de usenet-fr: http://www.usenet-fr.news.eu.org