std:: bsearch

Findet ein Element, das dem durch key referenzierten Element entspricht, in einem Array, auf das ptr zeigt. Das Array enthält count Elemente von jeweils size Bytes und muss bezüglich des durch key referenzierten Objekts partitioniert sein, d.h. alle Elemente, die kleiner vergleichen, müssen vor allen Elementen erscheinen, die gleich vergleichen, und diese müssen vor allen Elementen erscheinen, die größer vergleichen als das Schlüsselobjekt. Ein vollständig sortiertes Array erfüllt diese Anforderungen. Die Elemente werden mittels der durch comp referenzierten Funktion verglichen.

Das Verhalten ist undefiniert, wenn das Array nicht bereits in aufsteigender Reihenfolge bezüglich des Schlüssels partitioniert ist, gemäß demselben Kriterium, das comp verwendet.

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

Parameter

Rückgabewert

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

Hinweise

Trotz des Namens verlangen weder die C- noch die POSIX-Standards, dass diese Funktion mittels binärer Suche implementiert wird oder geben irgendwelche Komplexitätsgarantien.

Die beiden Überladungen, die von der C++-Standardbibliothek bereitgestellt werden, sind unterschiedlich, weil die Typen des Parameters comp unterschiedlich sind ( Sprachbindung 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