Funciones de búsqueda binaria en C++ STL (binary_search, lower_bound y upper_bound)

La búsqueda binaria es un componente importante en la programación competitiva o cualquier competencia algorítmica, tener conocimiento de las funciones abreviadas reduce el tiempo para codificarlas. Esta búsqueda solo funciona cuando el contenedor está ordenado . Las funciones relacionadas se describen a continuación.
1.binary_search(start_ptr, end_ptr, num) : esta función devuelve un booleano verdadero si el elemento está presente en el contenedor; de lo contrario, devuelve falso.
 

// C++ code to demonstrate the working of binary_search()
 
#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    // initializing vector of integers
    vector<int> arr = {10, 15, 20, 25, 30, 35};
     
    // using binary_search to check if 15 exists
    if (binary_search(arr.begin(), arr.end(), 15))
       cout << "15 exists in vector";
    else
       cout << "15 does not exist";
      
    cout << endl;
     
    // using binary_search to check if 23 exists
    if (binary_search(arr.begin(), arr.end(), 23))
         cout << "23 exists in vector";
    else
         cout << "23 does not exist";
      
    cout << endl;   
}

Producción: 
 

15 exists in vector
23 does not exist

2. lower_bound(start_ptr, end_ptr, num) : devuelve el puntero a la » posición de num » si el contenedor contiene 1 aparición de num. Devuelve el puntero a la » primera posición de num » si el contenedor contiene múltiples ocurrencias de num. Devuelve el puntero a la » posición de un número justo superior a num » si el contenedor no contiene la aparición de num, que es la posición del número cuando se inserta en la array ya ordenada y se ordena nuevamente. Restar el puntero a la primera posición, es decir, » vect.begin() » devuelve el índice real.
 

// C++ code to demonstrate the working of lower_bound()
#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    // initializing vector of integers
    // for single occurrence
    vector<int> arr1 = {10, 15, 20, 25, 30, 35};
     
    // initializing vector of integers
    // for multiple occurrences
    vector<int> arr2 = {10, 15, 20, 20, 25, 30, 35};
     
    // initializing vector of integers
    // for no occurrence
    vector<int> arr3 = {10, 15, 25, 30, 35};   
     
    // using lower_bound() to check if 20 exists
    // single occurrence
    // prints 2
    cout << "The position of 20 using lower_bound "
            " (in single occurrence case) : ";
    cout << lower_bound(arr1.begin(), arr1.end(), 20)
            - arr1.begin();
      
    cout << endl;
     
    // using lower_bound() to check if 20 exists
    // multiple occurrence
    // prints 2
    cout << "The position of 20 using lower_bound "
             "(in multiple occurrence case) : ";
    cout << lower_bound(arr2.begin(), arr2.end(), 20)
            - arr2.begin();
      
    cout << endl;
      
    // using lower_bound() to check if 20 exists
    // no occurrence
    // prints 2 ( index of next higher)
    cout << "The position of 20 using lower_bound "
             "(in no occurrence case) : ";
    cout << lower_bound(arr3.begin(), arr3.end(), 20)
            - arr3.begin();
      
    cout << endl;   
}

Producción: 
 

The position of 20 using lower_bound (in single occurrence case) : 2
The position of 20 using lower_bound (in multiple occurrence case) : 2
The position of 20 using lower_bound (in no occurrence case) : 2

3. upper_bound(start_ptr, end_ptr, num) : devuelve el puntero a la » posición del siguiente número más alto que num » si el contenedor contiene 1 aparición de num. Devuelve el puntero a la » primera posición del siguiente número más alto que la última aparición de num » si el contenedor contiene varias apariciones de num. Devuelve el puntero a la » posición del siguiente número más alto que num » si el contenedor no contiene la aparición de num. Restar el puntero a la primera posición, es decir, » vect.begin() » devuelve el índice real.

La búsqueda binaria es el algoritmo de búsqueda más eficiente.
 

// C++ code to demonstrate the working of upper_bound()
#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    // initializing vector of integers
    // for single occurrence
    vector<int> arr1 = {10, 15, 20, 25, 30, 35};
     
    // initializing vector of integers
    // for multiple occurrences
    vector<int> arr2 = {10, 15, 20, 20, 25, 30, 35};
     
    // initializing vector of integers
    // for no occurrence
    vector<int> arr3 = {10, 15, 25, 30, 35};
     
     
    // using upper_bound() to check if 20 exists
    // single occurrence
    // prints 3
    cout << "The position of 20 using upper_bound"
           " (in single occurrence case) : ";
    cout << upper_bound(arr1.begin(), arr1.end(), 20)
            - arr1.begin();
      
    cout << endl;
     
    // using upper_bound() to check if 20 exists
    // multiple occurrence
    // prints 4
    cout << "The position of 20 using upper_bound "
             "(in multiple occurrence case) : ";
    cout << upper_bound(arr2.begin(), arr2.end(), 20)
            - arr2.begin();
      
    cout << endl;
      
    // using upper_bound() to check if 20 exists
    // no occurrence
    // prints 2 ( index of next higher)
    cout << "The position of 20 using upper_bound"
            " (in no occurrence case) : ";
    cout << upper_bound(arr3.begin(), arr3.end(), 20)
           - arr3.begin();
      
    cout << endl;   
}

Producción: 
 

The position of 20 using upper_bound (in single occurrence case) : 3
The position of 20 using upper_bound (in multiple occurrence case) : 4
The position of 20 using upper_bound (in no occurrence case) : 2

Complejidad de tiempo: O (logN) – donde N es el número de elementos en la array.

Este artículo es una contribución de Manjeet Singh (HBD.N) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@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.