std::bsearch en C++

Conceptos básicos de la búsqueda binaria

std::bsearch busca un elemento en una array ordenada. Encuentra un elemento igual al elemento al que apunta key en una array a la que apunta ptr.
Si la array contiene varios elementos que comp indicarían como iguales al elemento buscado, entonces no se especifica qué elemento devolverá la función como resultado.
Sintaxis:

void* bsearch( const void* key, const void* ptr, std::size_t count,
               std::size_t size, * comp );

Parameters :
key     -    element to be found
ptr     -    pointer to the array to examine
count    -    number of element in the array
size    -    size of each element in the array in bytes
comp    -    comparison function which returns ?a negative integer value if 
             the first argument is less than the second,
             a positive integer value if the first argument is greater than the second
             and zero if the arguments are equal.

Return value :
Pointer to the found element or null pointer if the element has not been found.

Implementando el predicado binario comp :

// Binary predicate which returns 0 if numbers found equal
int comp(int* a, int* b)
{
  
    if (*a < *b)
        return -1;
  
    else if (*a > *b)
        return 1;
  
    // elements found equal
    else
        return 0;
}

Implementación

// CPP program to implement
// std::bsearch
#include <bits/stdc++.h>
  
// Binary predicate
int compare(const void* ap, const void* bp)
{
    // Typecasting
    const int* a = (int*)ap;
    const int* b = (int*)bp;
  
    if (*a < *b)
        return -1;
    else if (*a > *b)
        return 1;
    else
        return 0;
}
  
// Driver code
int main()
{
    // Given array
    int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
  
    // Size of array
    int ARR_SIZE = sizeof(arr) / sizeof(arr[0]);
  
    // Element to be found
    int key1 = 4;
  
    // Calling std::bsearch
    // Typecasting the returned pointer to int
    int* p1 = (int*)std::bsearch(&key1, arr, ARR_SIZE, sizeof(arr[0]), compare);
  
    // If non-zero value is returned, key is found
    if (p1)
        std::cout << key1 << " found at position " << (p1 - arr) << '\n';
    else
        std::cout << key1 << " not found\n";
  
    // Element to be found
    int key2 = 9;
  
    // Calling std::bsearch
    // Typecasting the returned pointer to int
    int* p2 = (int*)std::bsearch(&key2, arr, ARR_SIZE, sizeof(arr[0]), compare);
  
    // If non-zero value is returned, key is found
    if (p2)
        std::cout << key2 << " found at position " << (p2 - arr) << '\n';
    else
        std::cout << key2 << " not found\n";
}

Producción:

4 found at position 3
9 not found

Dónde usar: la búsqueda binaria se puede usar en datos ordenados donde se encuentra una clave. Se puede utilizar en casos como el cálculo de la frecuencia de una clave en una lista ordenada.

¿Por qué búsqueda binaria?
La búsqueda binaria es mucho más eficaz que la búsqueda lineal porque reduce a la mitad el espacio de búsqueda en cada paso. Esto no es significativo para nuestra array de longitud 9. Aquí, la búsqueda lineal toma como máximo 9 pasos y la búsqueda binaria toma como máximo 4 pasos. Pero considere una array con 1000 elementos, aquí la búsqueda lineal toma como máximo 1000 pasos, mientras que la búsqueda binaria toma como máximo 10 pasos.
Para mil millones de elementos, la búsqueda binaria encontrará nuestra clave en un máximo de 30 pasos.

Artículo relacionado: std::binary_search
Este artículo es una contribución de Rohit Thapliyal . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.