std::bsearch

void* bsearch( const void* key, const void* ptr, std::size_t count,
               std::size_t size, /* c-compare-pred */* comp );

void* bsearch( const void* key, const void* ptr, std::size_t count,
               std::size_t size, /* compare-pred */* comp );

void* bsearch( void* key, const void* ptr, std::size_t count,
               std::size_t size, /* c-compare-pred */* comp );

void* bsearch( void* key, const void* ptr, std::size_t count,
               std::size_t size, /* compare-pred */* comp );

extern "C" using /* c-compare-pred */ = int(const void*, const void*);

extern "C++" using /* compare-pred */ = int(const void*, const void*);

Recherche 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 chacun et doit être partitionné par rapport à l'objet pointé par key, c'est-à-dire que tous les éléments qui comparent inférieurs doivent apparaître avant tous les éléments qui comparent égaux, et ceux-ci doivent apparaître avant tous les éléments qui comparent supérieurs à l'objet clé. Un tableau entièrement trié satisfait ces exigences. Les éléments sont comparés à l'aide de la fonction pointée par comp.

Si le tableau n'est pas déjà partitionné en ordre croissant par rapport à key, selon le même critère que celui utilisé par comp, le comportement est indéfini.

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.

Paramètres

Valeur de retour

Pointeur vers l'élément trouvé ou pointeur nul si l'élément n'a pas été trouvé.

Notes

Malgré son nom, ni la norme C ni la norme POSIX n'exigent que cette fonction soit implémentée à l'aide d'une recherche binaire ou ne fournissent de garanties de complexité.

Les deux surcharges fournies par la bibliothèque standard C++ sont distinctes car les types du paramètre comp sont distincts (la liaison de langage fait partie de son type).

Exemple

#include <array>
#include <cstdlib>
#include <iostream>

template<typename T>
int compare(const void *a, const void *b)
{
    const auto &arg1 = *(static_cast<const T*>(a));
    const auto &arg2 = *(static_cast<const T*>(b));
    const auto cmp = arg1 <=> arg2;
    return cmp < 0 ? -1
        :  cmp > 0 ? +1
        :  0;
}

int main()
{
    std::array arr{1, 2, 3, 4, 5, 6, 7, 8};
    
    for (const int key : {4, 8, 9})
    {
        const int* p = static_cast<int*>(
            std::bsearch(&key,
                arr.data(),
                arr.size(),
                sizeof(decltype(arr)::value_type),
                compare<int>));
        
        std::cout << "value " << key;
        if (p)
            std::cout << " found at position " << (p - arr.data()) << '\n';
        else
            std::cout << " not found\n";
    }
}

value 4 found at position 3
value 8 found at position 7
value 9 not found

Voir aussi