bsearch : recherche dichotomique dans un tableau trié
Prototype:
void * bsearch( const void *pval, const void *tab, size_t nt, size_t no, int(*fcmp) (const void *p1, const void *p2));
dans: <stdlib.h>
Description:
La fonction bsearch() effectue la recherche d'une valeur dans un tableau trié; on lui fournit la valeur recherchée, le tableau dans lequel s'effectue la recherche, la taille d'un élément de ce tableau, et enfin un pointeur sur la fonction servant à comparer deux éléments (fonction de comparaison pour laquelle le tableau est trié).
Description des paramètres:
- pval: adresse de la valeur
- tab: adresse du premier élément du tableau
- nt: nombre d'éléments du tableau
- no: taille, en octets, d'un élément du tableau
- fcmp: fonction définissant la comparaison entre deux éléments du tableau; elle reçoit les adresses p1 et p2 des éléments et renvoie:
- un entier négatif si *p1 est inférieur à *p2
- 0 si *p1 est égal à *p2
- un entier positif si *p1 est supérieur à *p2
Valeur renvoyée:
- NULL si la valeur n'est pas présente dans le tableau,
- l'adresse d'un élément égal à *pval, sinon
Voir aussi:
Portabilité:
Exemple:
<![CDATA[
#include <stdio.h>
#include <stdlib.h>
/* Fonction de comparaison d'entiers, par odre décroissant */
int cmpEntier( const void * pm1, const void * pm2);
int main (void) {
/* Exemple de tableau d'entiers trié par ordre décroissant */
static int ti[]={ 25, 23, 23, 21, 19, 17};
int i, val, *pe,
nti = sizeof(ti)/sizeof(ti[0]);
printf("Recherche dans le tableau trié:");
for (i=0; i<nti; i++) printf(" %d", ti[i]);
printf("\n");
do {
printf("Entrez un entier(fin sur 0): ");
scanf("%d",&val);
pe = (int *)bsearch( &val, ti, nti, sizeof(ti[0]), cmpEntier);
if( pe == NULL ) printf(" n'est pas dans le tableau\n");
else printf(" trouvé, adresse:%x indice:%d\n", pe, pe-ti);
} while( val!= 0);
return 0;
}
int cmpEntier( const void * p1, const void * p2){
/* comparaison pour ordre décroissant */
typedef const int * PEntierConstant;
PEntierConstant pi1 = (PEntierConstant)p1,
pi2 = (PEntierConstant)p2;
return *pi2 - *pi1 ;
}
]]>