La fonction bsearch () en C ++ effectue une recherche binaire d'un élément dans un tableau d'éléments et renvoie un pointeur vers l'élément s'il est trouvé.
La fonction bsearch () nécessite tous les éléments inférieurs à l'élément à rechercher à gauche de celui-ci dans le tableau.
De même, tous les éléments supérieurs à l'élément à rechercher doivent être à sa droite dans le tableau. Cette condition est remplie si le tableau est trié par ordre croissant.
prototype bsearch ()
void * bsearch (const void * key, const void * base, size_t num, size_t size, int (* compare) (const void *, const void *));
La fonction est définie dans le fichier d'en-tête.
La fonction bsearch () recherche la clé dans la base du tableau. Tous les éléments inférieurs à la clé doivent apparaître avant lui dans la base du tableau. De même, tous les éléments supérieurs à la clé doivent apparaître après lui dans la base.
Pour effectuer la recherche, la fonction bsearch () effectue une série d'appels à la fonction pointée par compare avec key comme premier argument et un élément du tableau comme second argument.
Paramètres de bsearch ()
- clé: pointeur vers l'élément à rechercher
- base: pointeur vers le premier élément du tableau
- num: nombre d'élément dans le tableau
- size: taille en octets de chaque élément du tableau
- compare: un pointeur vers une fonction qui compare deux éléments. Il retourne
- un entier négatif si le premier argument est inférieur au second
- un entier positif si le premier argument est supérieur au second
- zéro si les deux arguments sont égaux
key est passé comme premier argument et un élément du tableau est passé comme second argument. Le prototype de la fonction de comparaison ressemble à:
int compare (const void * a, const void * b);
bsearch () Valeur de retour
La fonction bsearch () renvoie:
- Pointeur vers l'élément trouvé. Si plus d'un élément correspondant est trouvé, l'adresse d'élément que la fonction retournera comme résultat n'est pas spécifiée.
- Pointeur nul si l'élément n'est pas trouvé.
Exemple 1: Comment fonctionne la fonction bsearch ()?
#include #include using namespace std; int compare(const void* a, const void* b) ( const int* x = (int*) a; const int* y = (int*) b; return (*x - *y); ) int main() ( const int num = 10; int arr(num) = (5,9,10,14,16,19,21,26,29,31); int key1 = 10; int *p1 = (int*)bsearch(&key1,arr,num,sizeof(int),compare); if(p1 == NULL) cout << key1 << " not found " << endl; else cout << key1 << " found at position " << (p1-arr) << endl; int key2 = 15; int *p2 = (int*)bsearch(&key2,arr,num,sizeof(int),compare); if(p2 == NULL) cout << key2 << " not found " << endl; else cout << key2 << " found at position " << (p2-arr) << endl; return 0; )
Lorsque vous exécutez le programme, la sortie sera:
10 trouvé à la position 2 15 non trouvé
Exemple 2: Comment la fonction bsearch () fonctionne pour plusieurs éléments correspondants?
#include #include using namespace std; int compare(const void* a, const void* b) ( const int* x = (int*) a; const int* y = (int*) b; return (*x - *y); ) int main() ( const int num = 10; int arr(num) = (2,3,5,7,8,10,14,14,14,15); int key = 14; int *p = (int*)bsearch(&key,arr,num,sizeof(int),compare); if(p == NULL) cout << key << " not found " << endl; else /* 14 occurs at position 6,7 and 8*/ cout << key << " found at position " << (p-arr) << endl; return 0; )
Lorsque vous exécutez le programme, une sortie possible sera:
14 trouvé à la position 7
