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.