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*);

Sucht ein Element, das gleich dem Element ist, auf das key zeigt, in einem Array, auf das ptr zeigt. Das Array enthält count Elemente von jeweils size Bytes und muss in Bezug auf das Objekt, auf das key zeigt, partitioniert sein, d.h. alle Elemente, die kleiner sind als, müssen vor allen Elementen erscheinen, die gleich sind, und diese müssen vor allen Elementen erscheinen, die größer sind als das Schlüsselobjekt. Ein vollständig sortiertes Array erfüllt diese Anforderungen. Die Elemente werden mit der Funktion verglichen, auf die comp zeigt.

Wenn das Array nicht bereits in aufsteigender Reihenfolge in Bezug auf key partitioniert ist, gemäß demselben Kriterium, das comp verwendet, ist das Verhalten undefiniert.

Wenn das Array mehrere Elemente enthält, die comp als gleich dem gesuchten Element anzeigen würde, dann ist es nicht spezifiziert, welches Element die Funktion als Ergebnis zurückgibt.

Parameter

Rückgabewert

Zeiger auf das gefundene Element oder Nullzeiger, wenn das Element nicht gefunden wurde.

Hinweise

Trotz des Namens verlangen weder der C- noch der POSIX-Standard, dass diese Funktion mittels binärer Suche implementiert wird, noch machen sie irgendwelche Komplexitätsgarantien.

Die beiden von der C++-Standardbibliothek bereitgestellten Überladungen unterscheiden sich, da sich die Typen des Parameters comp unterscheiden (Sprachverknüpfung ist Teil seines Typs).

Beispiel

#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

Siehe auch