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

Encuentra un elemento igual al elemento apuntado por key en un arreglo apuntado por ptr. El arreglo contiene count elementos de size bytes cada uno y debe estar particionado con respecto al objeto apuntado por key, es decir, todos los elementos que comparan menores que deben aparecer antes que todos los elementos que comparan iguales a, y estos deben aparecer antes que todos los elementos que comparan mayores que el objeto clave. Un arreglo completamente ordenado satisface estos requisitos. Los elementos se comparan usando la función apuntada por comp.

Si el arreglo no está ya particionado en orden ascendente con respecto a key, según el mismo criterio que comp utiliza, el comportamiento no está definido.

Si el arreglo contiene varios elementos que comp indicaría como iguales al elemento buscado, entonces no se especifica qué elemento devolverá la función como resultado.

Parámetros

Valor de retorno

Puntero al elemento encontrado o puntero nulo si el elemento no ha sido encontrado.

Notas

A pesar del nombre, ni el estándar C ni el de POSIX requieren que esta función se implemente usando búsqueda binaria ni hacen ninguna garantía de complejidad.

Las dos sobrecargas proporcionadas por la biblioteca estándar de C++ son distintas porque los tipos del parámetro comp son distintos (enlace de lenguaje es parte de su tipo).

Ejemplo

#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

Véase también