"candide" <candide@free.invalid> a écrit dans le message de news:
48e3bd91$0$29457$426a74cc@news.free.fr...

Antoine Leca a écrit :

2) C'est un peu comme avec les propositions des politiques, j'aime bien
connaître le détail, histoire de voir le coût réel du supplément « non
excessif » ; entre autres questions qui me viennent à l'esprit, serait-ce
un
paramètre supplémentaire ? retourner une structure ? avec ou sans
restrict ?

Comment fonctionne une recherche dichotomique ? elle finit par encadrer la
clé par deux éléments consécutifs du tableau. En fait, pas tout à fait, si
la recherche a du bol, elle peut trouver la réponse avant d'avoir encadré
la clé. Par exemple si la liste est

int t[7]= {5, 9, 10, 19, 34, 34, 45}

le premier pivot est 19 (index (0+6)/2=3) et si la valeur cherchée est
justement 19, bsearch va s'arrêter là et renvoyer l'adresse
correspondante.

Par convention, on aurait pu décider que l'adresse renvoyée serait celle
de l'élément directement supérieur et NULL si on sort à droite du tableau
de valeur. Donc je ne vois pas ce que ça coûte, c'est epsilon en plus, on
renvoie un pointeur, pareil, ça marche même dans le cas où on a du bol.
Pour reprendre mon exemple ci-dessus, si la clé vaut 20, on renvoie t+4,
si la clé est 34, on renvoie t+4 ou t+5 et si la clé est 50 on renvoie
NULL.

Toutefois, ça présente l'inconvénient qu'on n'est pas sûr que la clé soit
présente lorsque le retour est non NULL et ça oblige l'utilisateur à
tester le retour pour être sûr.

De toute façon, si ça n'a pas été fait ainsi c'est que ça ne présentait
pas suffisamment d'intérêt pour une majorité de gens.

Je viens de regarder l'implémentation de Plauger et à ma grande surprise,
elle n'est pas récursive mais ça doit sans doute être plus efficace.

J'ai peur que cette dernière remarque soit à prendre au premier degré...
Faut-il que les étudiants soient bien intoxiqués de langages fonctionnels
pour imaginer systématiquement des solutions recursives aux problèmes les
plus simples ?

C'est en effet plus efficace de faire une simple boucle, mais il y a fort à
parier que les compilateurs modernes auraient détecté la récursion terminale
et produit un code similaire.

--
Chqrlie.