Fonction bsearch

La fonction at_quick_exit La fonction calloc

Entête à inclure

#include <stdlib.h>  // <cstdlib> en C++

Fonction bsearch

void * bsearch( const void * searchedValue, const void * arrayPtr, size_t elementCount, size_t elementSize, 
                int (*comparatorFunction)(const void *, const void *));

La fonction bsearch (binary search) permet de réaliser une recherche dichotomique d'une valeur dans un tableau d'éléments triés. L'intêret de la recherche dichotomique réside dans le fait qu'il n'est pas nécessaire de parcourir tous les éléments pour trouver la valeur recherchée : la recherche est donc plus rapide. En contrepartie, vous devez fournir un tableau préalablement trié.

Le tableau peut contenir des données quelconques. C'est pour cette raison que vous devez aussi fournir un pointeur sur une fonction de comparaison entre deux valeurs du tableaux ainsi que la taille des éléments du tableau. Cette fonction doit renvoyer une valeur négative si son premier élément est plus petit que le second, 0 si les deux éléments sont équivalents et une valeur positive si le premier élément est plus grand que le second. Voici, à titre d'exemple, à quoi pourrait ressembler une telle fonction.

 1 
 2 
 3 
 4 
 5 

int comparaisonFunction( const void * a, const void * b ) {
    if ( *(AType *)a <  *(AType *)b ) return -1;
    if ( *(AType *)a == *(AType *)b ) return 0;
    if ( *(AType *)a >  *(AType *)b ) return 1;
}

Paramètres

• searchedValue: un pointeur vers la données à rechercher. Comme cette valeur peut être d'un type quelconque, on a préféré opter pour un pointeur vers cette donnée.

• arrayPtr: un pointeur vers le tableaux de valeurs dans lequel effectuer la recherche.

• elementCount: le nombre d'éléments contenu dans le tableau.

• elementSize: la taille, exprimée en nombre d'octets, d'une donnée contenu dans le tableau.

• comparatorFunction: la fonction de comparaison de deux données du tableau.Cette fonction doit renvoyer une valeur négative si son premier élément est plus petit que le second, 0 si les deux éléments sont équivalents et une valeur positive si le premier élément est plus grand que le second.

Valeur de retour

Si l'élément recherché est présent dans le tableau, un pointeur vers une occurence (mais pas forcément la première, étant donné la recherche dichotomique) de l'élément vous sera retourné. Dans le cas contraire, un pointeur nul (NULL) sera renvoyé.

Exemple de code

 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 
 43 
 44 

#include <stdio.h>
#include <stdlib.h>

#define ARRAY_SIZE 10

/* 
 * Une fonction de comparaison de deux entiers.
 * Elle renvoie une valeur négative si a<b, nulle si a==b et positive si a>b.
 */ 
int compareInt( const void * a, const void * b ) {
    return (*(const int *)a) - (*(const int *)b);
}

int main() {

    // On a un tableau de données entières.
    int data[ARRAY_SIZE] = { 10,90,40,50,30,20,60,80,70,100 };

    // Il faut absolument qu'il soit trié, donc on le trie.
    qsort( data, ARRAY_SIZE, sizeof(int), compareInt );

    // On vérifie que le tableau soit trié.
    printf( "[" );
    for( int i=0; i<ARRAY_SIZE; i++ ) {
        printf( "%d", data[i] );
        if ( i < ARRAY_SIZE-1 ) printf( ", " );
    }
    printf("]\n");

    // On recherche quelques valeurs dans le tableau.
    int searchedValue = 50;
    int * result = bsearch( &searchedValue, data, ARRAY_SIZE, sizeof(int), compareInt );
    printf( "%d est %sprésent dans le tableau.\n",
            searchedValue,
            result != NULL ? "" : "non " );

    searchedValue = 55;
    result = bsearch( &searchedValue, data, ARRAY_SIZE, sizeof(int), compareInt );
    printf( "%d est %sprésent dans le tableau.\n",
            searchedValue,
            result != NULL ? "" : "non " );

    return EXIT_SUCCESS;
}

Et voici les résultats produits par cet exemple :

$> gcc -o sample sample.c
$> ./sample
[10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
50 est présent dans le tableau.
55 est non présent dans le tableau.
$>

Sujets connexes

La fonction at_quick_exit La fonction calloc