std :: binary_search () en C ++

En este artículo, vamos a ver C ++ STL función binary_search () que utiliza el algoritmo de búsqueda binaria estándar para buscar un elemento dentro de un rango.

binary_search () como una función STL

Sintaxis:

bool binary_search (
ForwardIterator first,
ForwardIterator last,
const T& value);

Cuando,

  • ForwardIterator primera = iterador de inicio del intervalo de
  • ForwardIterator última = iterador a extremo de la gama
  • T & amp; valor = referencia a elemento que es de tipo de datos T buscar, T puede ser cualquier tipo de datos incorporado o tipo de datos definido por el usuario

class tipo: bool

  • verdad – si el elemento se encontró en el rango
  • Falso – Si el elemento no se encuentra en el rango

la sintaxis anterior se utiliza para comparar elementos que utilizan operadores de comparación estándar. Dos elementos a & amp; b se dice que son iguales si ((a & lt;! b) & amp; & amp;! (a & gt; b)).

También podemos definir el comparador class definida por el usuario comparar. La sintaxis con el comparador definida por el usuario es, como a continuación:

bool binary_search(
ForwardIterator first,
ForwardIterator last,
const T& val,
Comparator comp);

Uso de la sintaxis anterior dos elemnts a & amp; b sería igual si (comp (a & lt;! b) & amp; & amp; comp (a & gt;! b)).

1) Usando class comparador

#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<int> arr{ 3, 2, 1, 4, 5, 6, 7 };
//tp perform binary search we need sorted
//input array
sort(arr.begin(), arr.end());
int search_element = 4;
//ForwardIterator first=arr.begin()
//ForwardIterator last=arr.end()
//const T& val=search_element
if (binary_search(arr.begin(), arr.end(), search_element)) {
cout << "search_element " << search_element << " foundn";
}
else
cout << "search_element" << search_element << " not foundn";
search_element = 7;
//ForwardIterator first=arr.begin()
//ForwardIterator last=arr.begin()+arr.size()-1
//const T& val=search_element
if (binary_search(arr.begin(), arr.begin() + arr.size() - 1, search_element)) {
cout << "search_element " << search_element << " foundn";
}
else
cout << "search_element " << search_element << " not foundn";
return 0;
}

Salida:

search_element 4 found
search_element 7 not found

En el programa anterior, hemos comprobado que los casos y hemos utilizado el comparador class. No hay necesidad de mención, ya que utiliza el algoritmo de búsqueda binaria búsqueda class, necesitamos alimentación ordenadas única matriz.

Así como un pre-requisito clasificamos la matriz. La matriz ordenada es: [1,2,3,4,5,6,7]

Entonces Return la primera class, nuestra gama es todo el vector, y se volvió verdad se encuentra, ya que el elemento buscado 4 .

for la segunda default, nuestra gama es [1-6] como mencionamos el iterador final como arr.begin () + arr.size () – 1 que deja el último elemento 7 . Así elemento 7 no se encuentra registrado.

2) Usando la función de comparación definida por el usuario

Aquí hemos dado un uso default donde tenemos detalles estudiantes for cinco estudiantes. Al utilizar el comparador definida por el usuario que hemos comprobado si hay un estudiante con las marcas o no especificados.

#include <bits/stdc++.h>
using namespace std;
class student {
int score;
int roll;
string name;
public:
student()
{
score = 0;
roll = 0;
name = "";
}
student(int sc, int ro, string nm)
{
score = sc;
roll = ro;
name = nm;
}
int get_score()
{
return score;
}
int get_roll()
{
return roll;
}
string get_name()
{
return name;
}
};
//comparator for sorting
bool myfunc(student a, student b)
{
if (a.get_score() < b.get_score()) //no swap
return true;
else //swap
return false;
}
//comparator for binary search
//match found if !mycomp(a,b) && !mycomp(b,a)
bool mycomp(student a, student b)
{
if (a.get_score() < b.get_score())
return true;
return false;
}
int main()
{
vector<student> arr(5);
//1st student
arr[0] = student(80, 5, "XYZ"); //roll 5, marks 80
//2nd student
arr[1] = student(70, 10, "INC"); //roll 10, marks 70
//3rd student
arr[2] = student(85, 7, "HYU"); //roll 7, marks 85
//4th student
arr[3] = student(83, 1, "EFG"); //roll 1, marks 83
//5th student
arr[4] = student(81, 11, "ABC"); //roll 11, marks 81
//sort based on marks
//user-defined compartor=myfunc to sort
sort(arr.begin(), arr.end(), myfunc);
//find if any student exists who scored 81
student t1(81, -1, ""); //dummy search element just to search the student marks
if (binary_search(arr.begin(), arr.end(), t1, mycomp))
cout << "Student with marks 81 existsn";
else
cout << "Student with marks 81 doesn't existn";
//find if any student exists who scored 75
student t2(75, -1, ""); //dummy search element just to search the student marks
if (binary_search(arr.begin(), arr.end(), t2, mycomp))
cout << "Student with marks 75 existsn";
else
cout << "Student with marks 75 doesn't existn";
return 0;
}

Salida:

Student with marks 81 exists
Student with marks 75 doesn't exist

Aquí hemos clasificado en primer lugar el vector de los estudiantes usando la función de comparación definida por el usuario. Hemos definido una búsqueda binaria comparador for separada, aunque ambos tienen el mismo cuerpo. Hemos especificado sólo para subrayar el factor que ambos comparadores no se utilizan de la misma manera. En case de búsqueda, hay un partido de b / w T y Tb (T sea el tipo de datos) si los (a, b) & amp;! & Amp; ! Comp (b, a) donde a es elemento del vector y b es el elemento de búsqueda.

Así que en este artículo, se vio la eficiencia con que podemos utilizar binary_search a buscar elementos dentro de un rango, no importa qué tipo de objeto se trata. Incluso For el tipo de datos definido por el usuario, lo podemos hacer mediante el uso de un comparador definida por el usuario como se muestra arriba. Pero, la cosa case a recordar es que la lista de entrada debe ser ordenado (basado en la tecla). case ejemplo, ya estábamos buscando for las marcas, que ordena la lista de los estudiantes sobre la base de marcas.


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *