BSEARCH |
Recherche binaire |
|---|---|
| Langage C | stdlib.h |
Syntaxe
| void *bsearch(const void *key,const void *base, size_t num, size_t width, int(*compare)(const void *elem1,const 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 |
Retour
| Valeur | Description |
|---|---|
| NULL | Cette valeur permet d'indiquer la clef spécifié par le paramètre key n'a pas été trouvé. |
| pointeur | Ces valeurs permettent d'indiquer un pointeur sur une entrée du tableau correspondant à la clef de recherche spécifié par le paramètre key. |
Description
Cette fonction permet d'effectuer une recherche binaire (dichotomique) dans un tableau. Par conséquent, la fonction «void *bsearch(const void *key,const void *base, size_t num, size_t width, int(*compare)(const void *elem1,const void *elem2))» de la bibliothèque standard du langage de programmation C recherche dans un tableau d'éléments (un membre initialement pointé par le paramètre base), pour un membre correspondant à l'objet pointé par le paramètre key et la taille de chaque membre du tableau est spécifiée par le paramètre width.
Algorithme
|
MODULE BSEARCH(array, key, size, compare_function) low ← 0 high ← size - 1 BOUCLE TANT QUE low ≤ high FAIRE * Calcul de l'index du milieu mid ← low + (high - low) / 2 * Comparer l'élément clef avec l'élément au milieu result ← compare_function(key, array[mid]) SI result = 0 ALORS * Si les éléments sont égaux, retourner l'élément trouvé RETOURNE adresse de array[mid] * Retourner l'adresse de l'élément trouvé SINON SI result < 0 ALORS * Si la clef est inférieure, chercher dans la partie gauche high ← mid - 1 SINON * Si la clef est supérieure, chercher dans la partie droite low ← mid + 1 FIN SI FIN BOUCLE TANT QUE RETOURNE NULL * Si l'élément n'est pas trouvé, retourner NULL |
Remarques
- Le contenu du tableau passé comme paramètre doit être des valeurs comparable valide pour la fonction de comparaison spécifié par le paramètre compare sinon le résultat est imprévisible.
- Fonctionnement interne : Pour effectuer la recherche, la fonction bsearch effectue une série d'appels à comparer avec le paramètre key en utilisant un algorithme de recherche dichotomique comme premier paramètre et avec les éléments du tableau pointés par base comme second paramètre. Étant donné que cette fonction est optimisée pour utiliser un algorithme de recherche non linéaire (soit une recherche binaire), les éléments comparant moins que la clef key à l'aide du paramètre compare doivent précéder ceux se comparant plus un. Cette exigence est remplie par tout tableau ordonné avec les mêmes critères que ceux utilisés par le paramètre compare (comme s'ils étaient triés précédemment avec la fonction standard qsort).
- La fonction bsearch accède à l'objet pointé par la clef key un nombre de fois quelconque dans le tableau pointé à la base, mais ne modifie aucune valeurs.
- Complexité de recherche : Normalement, les recherches binaires peuvent être calculer avec une fonction logarithmiques avec une moyenne de fois correspondant à la formule suivante :
- Avant l'arrivée de la fonction bsearch_s proposé dans la norme C11, les programmeurs utilisant la fonction bsearch, utilisaient souvent des variables globales pour transmettre un contexte supplémentaire à la fonction de comparaison.
| log2(num) + 2 = nombre de fois |
Exemple
Voici quelques exemples typiques de l'utilisation de cette fonction :
Essayer maintenant !
- #include <stdio.h>
- #include <string.h>
- #include <stdlib.h>
-
- #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)) {
- printf("DEF est dans le tableau.\n");
- } else {
- printf("DEF n'est pas trouvé dans le tableau.\n");
- }
- 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.