Rechercher
 

Améliorations / Corrections

Vous avez des améliorations (ou des corrections) à proposer pour ce document : je vous remerçie par avance de m'en faire part, cela m'aide à améliorer le site.

Emplacement :

Description des améliorations :

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;
}
Exemple de fonction de comparaison de deux éléments du tableau.

Paramètres

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 compareLong( 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), compareLong );

    // 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), compareLong );
    printf( "%d est %sprésent dans le tableau.\n",
            searchedValue,
            result != NULL ? "" : "non " );

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

    return EXIT_SUCCESS;
}
Exemple d'utilisation de la fonction bsearch

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

qsort


La fonction at_quick_exit La fonction calloc