La función bsearch () en C ++ realiza una búsqueda binaria de un elemento en una matriz de elementos y devuelve un puntero al elemento si se encuentra.
La función bsearch () requiere que todos los elementos menores que el elemento se busquen a su izquierda en la matriz.
Asimismo, todos los elementos mayores que el elemento a buscar deben estar a su derecha en la matriz. Este requisito se cumple si la matriz se ordena en orden ascendente.
bsearch () prototipo
void * bsearch (const void * key, const void * base, size_t num, size_t size, int (* compare) (const void *, const void *));
La función se define en el archivo de encabezado.
La función bsearch () busca la clave en la base de la matriz. Todos los elementos menores que key deben aparecer antes en la base de la matriz. Asimismo, todos los elementos mayores que key deben aparecer después de él en base.
Para realizar la búsqueda, la función bsearch () realiza una serie de llamadas a la función señalada por compare con key como primer argumento y un elemento de la matriz como segundo argumento.
Parámetros de bsearch ()
- clave: puntero al elemento a buscar
- base: puntero al primer elemento de la matriz
- num: número de elemento en la matriz
- tamaño: tamaño en bytes de cada elemento de la matriz
- comparar: un puntero a una función que compara dos elementos. Vuelve
- un entero negativo si el primer argumento es menor que el segundo
- un entero positivo si el primer argumento es mayor que el segundo
- cero si ambos argumentos son iguales
key se pasa como primer argumento y un elemento de la matriz se pasa como segundo argumento. El prototipo de la función de comparación se ve así:
int compare (const void * a, const void * b);
bsearch () Valor de retorno
La función bsearch () devuelve:
- Puntero al elemento encontrado. Si se encuentra más de un elemento coincidente, no se especifica qué dirección del elemento devolverá la función como resultado.
- Puntero nulo si no se encuentra el elemento.
Ejemplo 1: ¿Cómo funciona la función bsearch ()?
#include #include using namespace std; int compare(const void* a, const void* b) ( const int* x = (int*) a; const int* y = (int*) b; return (*x - *y); ) int main() ( const int num = 10; int arr(num) = (5,9,10,14,16,19,21,26,29,31); int key1 = 10; int *p1 = (int*)bsearch(&key1,arr,num,sizeof(int),compare); if(p1 == NULL) cout << key1 << " not found " << endl; else cout << key1 << " found at position " << (p1-arr) << endl; int key2 = 15; int *p2 = (int*)bsearch(&key2,arr,num,sizeof(int),compare); if(p2 == NULL) cout << key2 << " not found " << endl; else cout << key2 << " found at position " << (p2-arr) << endl; return 0; )
Cuando ejecute el programa, la salida será:
10 encontrado en la posición 2 15 no encontrado
Ejemplo 2: ¿Cómo funciona la función bsearch () para más de un elemento coincidente?
#include #include using namespace std; int compare(const void* a, const void* b) ( const int* x = (int*) a; const int* y = (int*) b; return (*x - *y); ) int main() ( const int num = 10; int arr(num) = (2,3,5,7,8,10,14,14,14,15); int key = 14; int *p = (int*)bsearch(&key,arr,num,sizeof(int),compare); if(p == NULL) cout << key << " not found " << endl; else /* 14 occurs at position 6,7 and 8*/ cout << key << " found at position " << (p-arr) << endl; return 0; )
Cuando ejecute el programa, una posible salida será:
14 encontrado en la posición 7
