Los algoritmos de búsqueda lineal y binaria son 2 de los algoritmos más usados para encontrar elementos en una estructura de datos.
La búsqueda lineal probablemente es sencilla de implementar e intuitiva. Básicamente consiste en buscar de manera secuencial un elemento, es decir, preguntar si el elemento buscado es igual al primero, segundo, tercero y así sucesivamente hasta encontrar el deseado. Entonces este algoritmo tiene una complejidad de O(n).
La búsqueda binaria al igual que otros algoritmos como el quicksort utiliza la técnica divide y vencerás. Uno de los requisitos antes de ejecutar la búsqueda binaria, es que el conjunto de elementos debe de estar ordenado. Supongamos que tenemos el siguiente array.
57 53 21 37 17 36 22 3 44 97 89 26 31 47 8 17
Debemos ordenarlo
3 8 17 17 21 22 26 31 36 37 44 47 53 57 89 97
¿Como funciona la búsqueda binaria?
Necesitamos una seria de datos para realizar la búsqueda: El elemento en la posición inicio, fin, medio. Y porsupuesto el tamaño del vector y elemento que queremos buscar.
inicio = 0;
fin = tam – 1;
medio = (inicio + fin) / 2;
Preguntamos si el elemento buscado es igual al elemento que se encuentra en la posicion medio del array, si es afirmativo ya encontramos el elemento y no hay nada más que hacer.
if(buscado == array[medio]){
cout << "Se encuentra en la posicion " << medio + 1 << endl;
return array[medio];
}
Si no es así. Preguntamos si el elemento que se encuentra en la posición medio es mayor al elemento buscado, si es afirmativo y como el array está ordenado, quiere decir que elemento buscado es menor al del medio. Entonces ahora solo buscaríamos en esa división del array,
por lo tanto, el fin ahora sería el elemento anterior al medio.
if(array[medio] > buscado){
fin = medio - 1;
}
De lo contrario quiere decir que elemento buscado es mayor al del medio, entonces debemos buscar en la otra división del array, por lo tanto el inicio sería el elemento posterior al medio.
else {
inicio = medio + 1;
}
Con cualquiera de estas 2 operaciones descartamos la otra mitad del array y por lo tanto reducimos notablemente el número de iteraciones.
Por lo tanto, en cada iteración, la búsqueda se reduce a la mitad del array. Realizamos esto en un bucle mientras el inicio sea menor o igual al fin.
El algoritmo de búsqueda binaria tiene una complejidad de O(log n).
Veamos la implementación de la búsqueda lineal y binaria en C++.
Nota: Para realizar la búsqueda binaria, estoy incluyendo el archivo que contiene el algoritmo de ordenamiento quicksort, para no volver a escribirlo y así reutilizar código.
#include “quicksort.h”
Aquí tienen el código del algoritmo y una breve explicación. Retiren el main para utilizarlo en otros programas.
#include <iostream>
#include "quicksort.h"
using namespace std;
int busqueda_lineal(int *array,int buscado,int tam)
{
for(int i=0;i<tam;i++){
if(buscado==array[i]){
cout << "Se encuentra en la posicion " << i+1 << endl;
}
}
}
int busqueda_binaria(int *array, int buscado, int tam)
{
int medio, inicio, fin;
inicio = 0;
fin = tam-1;
while(inicio <= fin){
medio = (inicio + fin) / 2;
if(buscado == array[medio]){
cout << "Se encuentra en la posicion " << medio + 1 << endl;
return array[medio];
} else{
if(array[medio] > buscado){
fin = medio - 1;
} else {
inicio = medio + 1;
}
}
}
return -1;
}
void imprimir(int *array,int tam)
{
for(int i=0;i<tam;i++){
cout << array[i] << " ";
}
cout << endl << endl;
}
int main()
{
int tam;
int buscado;
cout << "Ingresa el tamanyo del array" << endl;
cin >> tam;
int array[tam];
srand(time(NULL));
for(int i=0;i<tam;i++){
array[i] = rand() % 100;
}
cout << endl;
cout << "Array al inicio " << endl;
imprimir(array,tam);
cout << "Ingresa el elemento a buscar (Busqueda lineal) ";
cin >>buscado;
busqueda_lineal(array,buscado,tam);
cout << "Array ordenado " << endl;
quicksort(array,0,tam);
imprimir(array,tam);
cout << "Ingresa el elemento a buscar (Busqueda binaria) ";
cin >>buscado;
busqueda_binaria(array,buscado,tam);
return 0;
}
Ejemplo de la salida del programa:
Ingresa el tamanyo del array 16 Array al inicio 57 53 21 37 17 36 22 3 44 97 89 26 31 47 8 17 Ingresa el elemento a buscar (Busqueda lineal) 36 El elemento se encuentra en la posicion 6 Array ordenado 3 8 17 17 21 22 26 31 36 37 44 47 53 57 89 97 Ingresa el elemento a buscar (Busqueda binaria) 89 El elemento se encuentra en la posicion 15
Recent Comments