Namespaces
Variants

bsearch, bsearch_s

From cppreference.net
C
Algorithms
(C11)
bsearch bsearch_s
(C11)
Défini dans l'en-tête <stdlib.h>
void * bsearch ( const void * key, const void * ptr, size_t count, size_t size,
int ( * comp ) ( const void * , const void * ) ) ;
(1)
void * bsearch_s ( const void * key, const void * ptr, rsize_t count, rsize_t size,

int ( * comp ) ( const void * , const void * , void * ) ,

void * context ) ;
(2) (depuis C11)
/*QVoid*/ * bsearch ( const void * key, /*QVoid*/ * ptr, size_t count, size_t size,
int ( * comp ) ( const void * , const void * ) ) ;
(3) (depuis C23)
/*QVoid*/ * bsearch_s ( const void * key, /*QVoid*/ * ptr, rsize_t count, rsize_t size,

int ( * comp ) ( const void * , const void * , void * ) ,

void * context ) ;
(4) (depuis C23)
1) Trouve un élément égal à l'élément pointé par key dans un tableau pointé par ptr . Le tableau contient count éléments de size octets et doit être partitionné par rapport à key , c'est-à-dire que tous les éléments qui se comparent comme inférieurs doivent apparaître avant tous les éléments qui se comparent comme égaux, et ceux-ci doivent apparaître avant tous les éléments qui se comparent comme supérieurs à l'objet clé. Un tableau entièrement trié satisfait ces exigences. Les éléments sont comparés en utilisant la fonction pointée par comp . Le comportement est indéfini si le tableau n'est pas déjà partitionné par rapport à *key en ordre ascendant selon le même critère que comp utilise.
2) Identique à (1) , sauf que l'argument d'état supplémentaire context est passé à comp et que les erreurs suivantes sont détectées à l'exécution et appellent la fonction constraint handler actuellement installée :
  • count ou size est supérieur à RSIZE_MAX
  • key , ptr ou comp est un pointeur nul (sauf si count est zéro)
Comme pour toutes les fonctions à vérification de limites, bsearch_s (et la macro générique correspondante) (depuis C23) n'est garantie d'être disponible que si __STDC_LIB_EXT1__ est défini par l'implémentation et si l'utilisateur définit __STDC_WANT_LIB_EXT1__ à la constante entière 1 avant d'inclure <stdlib.h> .
3,4) Macros génériques équivalents à (1) et (2) respectivement. Soit T un type d'objet non qualifié (incluant void ).
  • Si ptr est de type const T * , le type de retour est const void * .
  • Sinon, si ptr est de type T * , le type de retour est void * .
  • Sinon, le comportement est indéfini.
Si une définition de macro de chacune de ces fonctions génériques est supprimée pour accéder à une fonction réelle (par exemple si ( bsearch ) , ( bsearch_s ) , ou un pointeur de fonction est utilisé), la déclaration de fonction réelle (1) ou (2) devient visible.

Si le tableau contient plusieurs éléments que comp indiquerait comme égaux à l'élément recherché, alors il n'est pas spécifié quel élément la fonction retournera comme résultat.

Les utilisations directes des fonctions réelles (1) et (2) sont dépréciées.

(depuis C23)

Table des matières

Paramètres

key - pointeur vers l'élément à rechercher
ptr - pointeur vers le tableau à examiner
count - nombre d'éléments dans le tableau
size - taille de chaque élément du tableau en octets
comp - fonction de comparaison qui renvoie un entier négatif si le premier argument est inférieur au second, un entier positif si le premier argument est supérieur au second et zéro si les arguments sont équivalents. key est passé comme premier argument, un élément du tableau comme second.

La signature de la fonction de comparaison doit être équivalente à ce qui suit :

int cmp ( const void * a, const void * b ) ;

La fonction ne doit pas modifier les objets qui lui sont passés et doit renvoyer des résultats cohérents lorsqu'elle est appelée pour les mêmes objets, indépendamment de leur position dans le tableau.

​

context - état du comparateur (par exemple, séquence de collationnement), passé à comp comme troisième argument

Valeur de retour

1) Pointeur vers un élément du tableau qui est égal à * key , ou pointeur nul si aucun élément n'a été trouvé.
2) Identique à (1) , sauf que le pointeur nul est également retourné en cas de violations des contraintes d'exécution.
3,4) Identique à (1) et (2) respectivement, sauf que la qualification cv est ajustée.

Notes

Malgré son nom, ni les normes C ni POSIX n'exigent que cette fonction soit implémentée en utilisant une recherche binaire ou ne fournissent aucune garantie de complexité.

Contrairement aux autres fonctions à vérification des limites, bsearch_s ne traite pas les tableaux de taille nulle comme une violation de contrainte d'exécution et indique plutôt l'élément non trouvé (l'autre fonction qui accepte les tableaux de taille nulle est qsort_s ).

Jusqu'à bsearch_s , les utilisateurs de bsearch utilisaient souvent des variables globales pour représenter l'état du comparateur.

Exemple

Exécuter ce code 
#include <stdlib.h>
#include <stdio.h>
struct data {
    int nr;
    char const *value;
} dat[] = {
    {1, "Foo"}, {2, "Bar"}, {3, "Hello"}, {4, "World"}
};
int data_cmp(void const *lhs, void const *rhs) 
{
    struct data const *const l = lhs;
    struct data const *const r = rhs;
    if (l->nr < r->nr) return -1;
    else if (l->nr > r->nr) return 1;
    else return 0;
    // return (l->nr > r->nr) - (l->nr < r->nr); // possible shortcut
    // return l->nr - r->nr; // erroneous shortcut (fails if INT_MIN is present)
}
int main(void) 
{
    struct data key = { .nr = 3 };
    struct data const *res = bsearch(&key, dat, sizeof dat / sizeof dat[0],
                                     sizeof dat[0], data_cmp);
    if (res) {
        printf("No %d: %s\n", res->nr, res->value);
    } else {
        printf("No %d not found\n", key.nr);
    }
}

Sortie : 

No 3: Hello

Références

  • Norme C17 (ISO/CEI 9899:2018) :
  • 7.22.5.1 La fonction bsearch (p: 258)
  • K.3.6.3.1 La fonction bsearch_s (p: 441-442)
  • Norme C11 (ISO/CEI 9899:2011) :
  • 7.22.5.1 La fonction bsearch (p: 355)
  • K.3.6.3.1 La fonction bsearch_s (p: 608-609)
  • Norme C99 (ISO/CEI 9899:1999) :
  • 7.20.5.1 La fonction bsearch (p : 318-319)
  • Norme C89/C90 (ISO/IEC 9899:1990) :
  • 4.10.5.1 La fonction bsearch

Voir aussi

(C11)
trie une plage d'éléments de type non spécifié
(fonction)
documentation C++ pour bsearch