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.
CPP
// 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.
CPP
// 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.
CPP
// 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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA