La búsqueda binaria es un algoritmo de búsqueda ampliamente utilizado que requiere que la array se ordene antes de aplicar la búsqueda. La idea principal detrás de este algoritmo es seguir dividiendo la array por la mitad (divide y vencerás) hasta que se encuentre el elemento o se agoten todos los elementos.
Funciona comparando el elemento del medio de la array con nuestro objetivo; si coincide, devuelve verdadero; de lo contrario, si el término del medio es mayor que el objetivo, la búsqueda se realiza en la sub-array izquierda.
Si el término medio es menor que el objetivo, la búsqueda se realiza en el subarreglo derecho.
El prototipo para la búsqueda binaria es:
CPP
// CPP program to implement
// Binary Search in
// Standard Template Library (STL)
#include <algorithm>
#include <iostream>
using namespace std;
void show(int a[], int arraysize)
{
for (int i = 0; i < arraysize; ++i)
cout << a[i] << ",";
}
int main()
{
int a[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
int asize = sizeof(a) / sizeof(a[0]);
cout << "\nThe array is : \n";
show(a, asize);
cout << "\n\nLet's say we want to search for ";
cout << "\n2 in the array So, we first sort the array";
sort(a, a + asize);
cout << "\n\nThe array after sorting is : \n";
show(a, asize);
cout << "\n\nNow, we do the binary search";
if (binary_search(a, a + 10, 2))
cout << "\nElement found in the array";
else
cout << "\nElement not found in the array";
cout << "\n\nNow, say we want to search for 10";
if (binary_search(a, a + 10, 10))
cout << "\nElement found in the array";
else
cout << "\nElement not found in the array";
return 0;
}
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