bsearch

Article
06/09/2015

Effectue une recherche binaire d'un tableau trié. Des versions plus sécurisées de ces fonctions sont disponibles ; consultez bsearch_s.

void *bsearch( 
   const void *key,
   const void *base,
   size_t num,
   size_t width,
   int ( __cdecl *compare ) (const void *key, const void *datum) 
);

Paramètres

key
Objet à rechercher.
base
Pointeur vers la base de données de recherche.
num
Nombre d'éléments
width
Largeur des éléments.
compare
Fonction de rappel qui compare deux éléments. Le premier es un pointeur vers la clé pour la recherche et le second est un pointeur sur l'élément de tableau à comparer à la clé.

Valeur de retour

bsearch retourne un pointeur vers une occurrence de keydans le tableau pointé par base. Si key n'y figure pas, la fonction retourne la valeur NULL. Si la table n'est pas dans l'ordre de tri croissant ou si elle contient les enregistrements en double avec des clés identiques, le résultat est imprévisible.

Notes

La fonction bsearch effectue une recherche binaire d'un tableau trié d'éléments num, chacun de width octets en taille. La valeur base est un pointeur vers la base de la table à rechercher, puis key est la valeur désirée. Le paramètre compare est un pointeur vers une routine fournie à l'utilisateur qui compare la clé requise à un élément du tableau et retourne l'une des valeurs suivantes en spécifiant leur relation :

Valeur retournée par la routine compare	Description
< 0	La clé est inférieur à l'élément du tableau.
0	La clé est égale à l'élément du tableau.
> 0	La clé est supérieure à l'élément du tableau.

Cette fonction valide ses paramètres. Si compare , key ou numest NULL , ou si base est NULL et *num est différent de zéro, ou si widthest nulle, le gestionnaire de paramètre non valide est appelé, comme décrit dans Validation de paramètre. Si l'exécution est autorisée à se poursuivre, errno est défini à EINVAL et la fonction retourne NULL.

Configuration requise

Routine	En-tête requis
bsearch	<stdlib.h> et <malloc.h>

Pour plus d'informations sur la compatibilité, consultez Compatibilité dans l'introduction.

Exemple

Ce programme trie un tableau de chaînes avec qsort , puis utilise des bsearch pour rechercher le mot « cat ».

// crt_bsearch.c
#include <search.h>
#include <string.h>
#include <stdio.h>

int compare( char **arg1, char **arg2 )
{
   /* Compare all of both strings: */
   return _strcmpi( *arg1, *arg2 );
}

int main( void )
{
   char *arr[] = {"dog", "pig", "horse", "cat", "human", "rat", "cow", "goat"};
   char **result;
   char *key = "cat";
   int i;

   /* Sort using Quicksort algorithm: */
   qsort( (void *)arr, sizeof(arr)/sizeof(arr[0]), sizeof( char * ), (int (*)(const 
   void*, const void*))compare );

   for( i = 0; i < sizeof(arr)/sizeof(arr[0]); ++i )    /* Output sorted list */
      printf( "%s ", arr[i] );

   /* Find the word "cat" using a binary search algorithm: */
   result = (char **)bsearch( (char *) &key, (char *)arr, sizeof(arr)/sizeof(arr[0]),
                              sizeof( char * ), (int (*)(const void*, const void*))compare );
   if( result )
      printf( "\n%s found at %Fp\n", *result, result );
   else
      printf( "\nCat not found!\n" );
}