BSEARCH |
Recherche binaire |
|---|---|
| Langage C++ | cstdlib (stdlib.h) |
Syntaxe
| void *bsearch(const void *key,const void *base, size_t num, size_t width, int(*compare)(const void *elem1,const void void *elem2)) |
Paramètres
| Nom | Description |
|---|---|
| key | Ce paramètre permet d'indiquer l'adresse de la valeur à rechercher |
| base | Ce paramètre permet d'indiquer l'adresse du tableau |
| num | Ce paramètre permet d'indiquer le nombre d'item que contient le tableau |
| width | Ce paramètre permet d'indiquer la taille d'un item du tableau |
| compare | Ce paramètre permet d'indiquer la fonction a utiliser pour la comparaison et doit retourner une valeur pour indiquer si les items sont inférieur, égale ou supérieur |
| elem1 | Ce paramètre permet d'indiquer le premier item fonction a utiliser pour la comparaison |
| elem2 | Ce paramètre permet d'indiquer le deuxième item fonction a utiliser pour la comparaison |
Description
Cette fonction effectue une recherche binaire (dichotomique) dans un tableau.
Remarques
- La fonction bsearch() effectue une recherche binaire sur le tableau trié pointé par base et renvoie un pointeur sur le premier membre correspondant à la clef pointée par key.
- Le nombre d'éléments dans le tableau est spécifié par num, et la taille (en octets) de chaque élément est décrite par width.
- La fonction pointée par compare est utilisée pour comparer un élément du tableau avec la clef. Le format de la fonction de comparaison doit être la suivante :
- Le tableau doit être trié par ordre croissant, l'adresse la plus basse contenant l'élément le plus bas.
- Si le tableau ne contient pas la clef, un pointeur null est renvoyé.
- Définition et utilité : La fonction bsearch permet d'effectuer une recherche binaire dans un tableau trié. Elle est définie dans l'entête <cstdlib> et permet de trouver rapidement la position d'un élément dans un tableau. La recherche binaire est particulièrement efficace dans des tableaux triés car elle réduit la complexité de la recherche à O(log n) par rapport à une recherche linéaire qui serait de complexité O(n).
- Fonction de comparaison : Le paramètre compare est une fonction de comparaison devant renvoyer une valeur négative si le premier élément est inférieur au second, une valeur positive si le premier élément est supérieur au second, et zéro si les éléments sont égaux. Cette fonction permet à bsearch de savoir comment comparer les éléments du tableau et d'effectuer la recherche binaire. Exemple de fonction de comparaison pour des entiers :
- Tableau trié requis : Pour que bsearch fonctionne correctement, le tableau d'entrée doit être trié. Si ce n'est pas le cas, les résultats seront indéfinis. La fonction ne trie pas le tableau, elle ne fait qu'effectuer la recherche binaire sur un tableau déjà trié. Cela signifie que vous devez être sûr que le tableau est correctement trié avant d'utiliser bsearch.
- Limitation de l'utilisation avec des types complexes : bsearch fonctionne avec des tableaux de type générique, car il prend des pointeurs void* pour les éléments du tableau et la clef. Cependant, cela signifie qu'il est nécessaire de gérer explicitement les conversions de types, en particulier pour les types complexes. Cela peut rendre son utilisation un peu moins intuitive et augmenter les risques d'erreurs de type si une gestion soignée n'est pas effectuée.
- Risque d'accès à des zones invalides : Comme bsearch renvoie un pointeur générique, il peut être nécessaire de faire attention lors de l'interprétation de ce pointeur, surtout si la recherche échoue. Si l'élément n'est pas trouvé, le résultat est nullptr. Mais si la fonction est mal utilisée et que vous tentez d'interpréter un pointeur non valide, cela peut entraîner des erreurs d'exécution.
- Alternatives en C++ moderne : Bien que bsearch soit une méthode efficace pour effectuer une recherche binaire dans des tableaux C, en C++ moderne, il existe des alternatives comme la fonction std::binary_search de la bibliothèque standard C++ (en C++11 et versions ultérieures). Cette fonction est plus intuitive à utiliser avec les conteneurs de la STL comme std::vector ou std::array, et elle ne nécessite pas de fonction de comparaison explicite si les éléments du conteneur sont déjà comparables. De plus, std::binary_search renvoie un booléen indiquant si l'élément a été trouvé, ce qui est souvent plus pratique que de travailler avec des pointeurs bruts.
| int func_name(const void *arg1, const void *arg2); |
Elle doit renvoyer les valeurs décrites dans le tableau suivant :
| Valeur | Description |
|---|---|
| < 0 (Moins que zéro) | Ces valeurs permettent d'indiquer que arg1 est inférieur à arg2. |
| 0 (Zéro) | Cette valeur permet d'indiquer que arg1 est égal à arg2. |
| > 0 (Supérieur à zéro) | Ces valeurs permettent d'indiquer que arg1 est supérieur à arg2. |
Exemple
Voici quelques exemples typiques de l'utilisation de cette fonction :
Essayer maintenant !
- #include <iostream>
- #include <cstring>
- #include <cstdlib>
-
- #define NUM_ELEMENT_ARRAY 7
- #define STR_LENGTH 5
-
- char strvalues[][STR_LENGTH] = {"ABC","DEF","GHI","JKL","MNO","PQR","STU"};
-
- int main()
- {
- if(NULL != (char*)bsearch("DEF", strvalues, NUM_ELEMENT_ARRAY, STR_LENGTH, (int(*)(const void*,const void*)) strcmp)) {
- std::cout << "DEF est dans le tableau." << std::endl;
- } else {
- std::cout << "DEF n'est pas trouvé dans le tableau." << std::endl;
- }
- return 0;
- }
on obtiendra le résultat suivant :
DEF est dans le tableau.Voir également
Langage de programmation - C++ - Référence de procédures et fonctions - qsort
Langage de programmation - C - Référence de procédures et fonctions - bsearch
Références
Langage C, Edition Micro-Application, Gehard Willms, 2001, ISBN: 2-7429-2008-0, page 730.
Borland C++ for Windows 4.0, Library Reference, Edition Borland, 1993, Part # BCP1240WW21772, page 44.
Dernière mise à jour : Lundi, le 3 août 2015