Namespaces
Variants

bsearch, bsearch_s

From cppreference.net
C
Algorithms
(C11)
bsearch bsearch_s
(C11)
Definido en el encabezado <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) (desde C11)
/*QVoid*/ * bsearch ( const void * key, /*QVoid*/ * ptr, size_t count, size_t size,
int ( * comp ) ( const void * , const void * ) ) ;
(3) (desde 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) (desde C23)
1) Encuentra un elemento igual al elemento apuntado por key en un array apuntado por ptr . El array contiene count elementos de size bytes y debe estar particionado con respecto a key , es decir, todos los elementos que se comparan como menores deben aparecer antes de todos los elementos que se comparan como iguales, y estos deben aparecer antes de todos los elementos que se comparan como mayores que el objeto clave. Un array completamente ordenado satisface estos requisitos. Los elementos se comparan usando la función apuntada por comp . El comportamiento es indefinido si el array no está ya particionado con respecto a *key en orden ascendente de acuerdo con el mismo criterio que comp utiliza.
2) Igual que (1) , excepto que el argumento de estado adicional context se pasa a comp y que los siguientes errores se detectan en tiempo de ejecución y llaman a la función constraint handler actualmente instalada:
  • count o size son mayores que RSIZE_MAX
  • key , ptr o comp son punteros nulos (a menos que count sea cero)
Como con todas las funciones con verificación de límites, bsearch_s (y el macro genérico correspondiente) (desde C23) solo se garantiza que esté disponible si __STDC_LIB_EXT1__ está definido por la implementación y si el usuario define __STDC_WANT_LIB_EXT1__ como la constante entera 1 antes de incluir <stdlib.h> .
3,4) Macros genéricas de tipo equivalentes a (1) y (2) respectivamente. Sea T un tipo de objeto no calificado (incluyendo void ).
  • Si ptr es de tipo const T * , el tipo de retorno es const void * .
  • De lo contrario, si ptr es de tipo T * , el tipo de retorno es void * .
  • De lo contrario, el comportamiento es indefinido.
Si se suprime la definición de macro de cada una de estas funciones genéricas para acceder a una función real (por ejemplo, si se usa ( bsearch ) , ( bsearch_s ) , o un puntero a función), la declaración de función real (1) o (2) se hace visible.

Si el array contiene varios elementos que comp indicaría como iguales al elemento buscado, entonces no está especificado cuál elemento devolverá la función como resultado.

Los usos directos de las funciones reales (1) y (2) están obsoletos.

(since C23)

Contenidos

Parámetros

key - puntero al elemento a buscar
ptr - puntero al array a examinar
count - número de elementos en el array
size - tamaño de cada elemento del array en bytes
comp - función de comparación que retorna un valor entero negativo si el primer argumento es menor que el segundo, un valor entero positivo si el primer argumento es mayor que el segundo y cero si los argumentos son equivalentes. key se pasa como primer argumento, un elemento del array como segundo.

La firma de la función de comparación debe ser equivalente a la siguiente:

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

La función no debe modificar los objetos pasados a ella y debe retornar resultados consistentes cuando se llama para los mismos objetos, independientemente de sus posiciones en el array.

​

context - estado del comparador (ej. secuencia de ordenación), pasado a comp como tercer argumento

Valor de retorno

1) Puntero a un elemento en el arreglo que compare igual a * key , o puntero nulo si no se ha encontrado dicho elemento.
2) Igual que (1) , excepto que el puntero nulo también se devuelve en caso de violaciones de restricciones en tiempo de ejecución.
3,4) Igual que (1) y (2) respectivamente, excepto que la calificación cv se ajusta.

Notas

A pesar del nombre, ni los estándares de C ni POSIX requieren que esta función se implemente mediante búsqueda binaria ni ofrecen garantías de complejidad.

A diferencia de otras funciones con verificación de límites, bsearch_s no trata los arreglos de tamaño cero como una violación de restricción en tiempo de ejecución y en su lugar indica que el elemento no se encontró (la otra función que acepta arreglos de tamaño cero es qsort_s ).

Hasta bsearch_s , los usuarios de bsearch frecuentemente utilizaban variables globales para representar el estado del comparador.

Ejemplo

Ejecutar este código 
#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);
    }
}

Salida: 

No 3: Hello

Referencias

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

Véase también

(C11)
ordena un rango de elementos con tipo no especificado
(función)
Documentación de C++ para bsearch