Cómo aplicar STL binary_search al vector de pares (clave, valor), dado que el vector está ordenado por su primer valor (clave) struct compare en el código contiene dos funciones que comparan la clave (elemento de búsqueda) con el primer elemento en el vector
CPP
/* C++ code to demonstrate how Binary Search
can be applied on a vector of pairs */
#include <bits/stdc++.h>
using namespace std;
struct compare {
bool operator()(const pair<int, int>& value,
const int& key)
{
return (value.first < key);
}
bool operator()(const int& key,
const pair<int, int>& value)
{
return (key < value.first);
}
};
int main()
{
// initializing the vector of pairs
vector<pair<int, int> > vect;
// insertion of pairs (key, value) in vector vect
vect.push_back(make_pair(1, 20));
vect.push_back(make_pair(3, 42));
vect.push_back(make_pair(4, 36));
vect.push_back(make_pair(2, 80));
vect.push_back(make_pair(7, 50));
vect.push_back(make_pair(9, 20));
vect.push_back(make_pair(3, 29));
// sorting the vector according to key
sort(vect.begin(), vect.end());
// printing the sorted vector
cout << "KEY" << '\t' << "ELEMENT" << endl;
for (pair<int, int>& x : vect)
cout << x.first << '\t' << x.second << endl;
// searching for the key element 3
cout << "search for key 3 in vector" << endl;
if (binary_search(vect.begin(), vect.end(),
3, compare()))
cout << "Element found";
else
cout << "Element not found";
return 0;
}
Producción:
KEY ELEMENT 1 20 2 80 3 29 3 42 4 36 7 50 9 20 search for key 3 in vector Element found
Complejidad del tiempo: O(n log n) (Como se usa la función sort())
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por cr7_bullet y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA