La función de biblioteca STL incorporada binary_search() para buscar si una string dada está presente o no en la array de strings dada. La búsqueda binaria es un enfoque de divide y vencerás. La idea detrás del algoritmo de búsqueda binaria es seguir dividiendo la array por la mitad hasta que se encuentre el elemento o se agoten todos los elementos. El elemento central de la array se compara con el valor objetivo, es decir, el valor que debe buscarse; si coincide, devuelve verdadero; de lo contrario, si el término central es mayor que el objetivo, la búsqueda se realiza en la subarray izquierda. Si el elemento del medio es menor que el objetivo, la búsqueda se realiza en el subarreglo derecho.
Ejemplo:
Input: arr[] = {“Geeks”, “For”, “GeeksForGeek”}
Search “Geeks”
Output: String Founded in array
Sintaxis:
binary_search(starting_address, ending_address, value_of_string)
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program to implement Binary
// Search in Standard Template Library (STL)
#include <algorithm>
#include <iostream>
using namespace std;
void show_array(string arr[], int arraysize)
{
for (int i = 0; i < arraysize; i++)
cout << arr[i] << ", ";
}
void binarySearch(string arr[], int size)
{
cout << "\nThe array is : \n";
show_array(arr, size);
// Sort string array a for binary search as prerequisite
sort(arr, arr + size);
// Finding for "Geeks"
cout << "\n\nSearching Result for \"Geeks\"";
if (binary_search(arr, arr + size, "Geeks"))
cout << "\nString Founded in array\n";
else
cout << "\nString not Founded in array\n";
// Finding for string str
string str = "Best";
cout << "\nSearching Result for \"Best\"";
if (binary_search(arr, arr + size, str))
cout << "\nString Found in array";
else
cout << "\nString not Found in array";
}
// Driver code
int main()
{
// Initialising string array a
string arr[] = { "Geeks", "For", "GeeksForGeek" };
// Find size of array arr
int size = sizeof(arr) / sizeof(arr[0]);
// Function call
binarySearch(arr, size);
return 0;
}
The array is : Geeks, For, GeeksForGeek, Searching Result for "Geeks" String Founded in array Searching Result for "Best" String not Found in array
Complejidad de tiempo: O(N*log N), donde N representa el número de elementos presentes en la array
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ajaymakvana y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA