"candide" <candide@free.invalid> a écrit dans le message de news:
48e5475f$0$26687$426a34cc@news.free.fr...

Charlie Gordon a écrit :

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.

Parles-en à Plauger, voilà ce qu'il en dit dans son livre sur la
bibliothèque standard (page 353) :

Function bsearch : (...). The logic is simple but easy to get wrong.

Je n'avais pas regardé "The Standard C Library" de Plauger, mais
j'avais bien le même point de vue :

"Il est encore facile de faire des erreurs d'implementation quand
on code bsearch pour le petit dej"

C'est exactement mon avis et c'est aussi pour ça que je trouve que c'est
une plaie à coder : un bsearch c'est une mécanique de précision.

C'est une mécanique de précision relativement simple, où s'applique
parfaitement l'adage de Saint-Exupéry : "La perfection est atteinte,
non pas lorsqu'il n'y a plus rien à ajouter, mais lorsqu'il n'y a plus
rien à retirer."

Néanmoins, je trouve le code de Plauger assez compliqué :

/* bsearch function */
#include <stdlib.h>

void *(bsearch)(const void *key, const void *base,
    size_t nelem, size_t size, _Cmpfun *cmp)
    {                   /* search sorted table by binary chop */
    const char *p = base;
    size_t n;

    for (p = base, n = nelem; 0 < n; )
        {               /* check midpoint of whatever is left */
        const size_t pivot = n >> 1;
        const char *const q = p + size * pivot;
        const int val = (*cmp)(key, q);

        if (val < 0)
            n = pivot;                  /* search below pivot */
        else if (val == 0)
            return ((void *)q);                      /* found */
        else
            {                           /* search above pivot */
            p = q + size;
            n -= pivot + 1;
            }
        }
    return (NULL);                                /* no match */
    }


Moi aussi.  Je le trouve peu élégant, surtout à cause des lourdeurs
inutiles comme les parenthèses dans ``return (NULL);'' ``return ((void
*)q);'', le const dans ``const size_t pivot'' et pire encore : ``const
char *const q''

Qualifier les variables locales avec const est sans intérêt dans un
code d'une page, et mettre const avant le type est peu lisible,
d'autant qu'on doitle mettre après l'étoile pour les pointeurs.

La boucle for est particulièrement lourdingue : l'affectation de p est
redondante avec la définition deux lignes plus haut, celle de n aurait
aussi dû se faire dans la définition, enfin l'ordre des arguments de <
est une ineptie : ``0 < n''.  Je n'aime pas non plus les accolades
indentées ni les commentaires cadrés à droite.

--
Chqrlie.