En este tutorial aprenderemos a implementar la Búsqueda Binaria en un arreglo ordenado, mediante el uso de las estructuras de control FOR, WHILE e IF.
En este tutorial aprenderemos a implementar la Búsqueda Binaria en un arreglo ordenado, mediante el uso de las estructuras de control FOR, WHILE e IF.
BÚSQUEDA BINARIA
La búsqueda de un elemento dentro de un array es una de las operaciones más importantes en el procesamiento de información, y permite la recuperación de datos. El caso de la Búsqueda Binaria, que es uno de las tantas búsquedas que existe, pero la más usada, está hecho para diferentes campos en el mundo laboral, como por ejemplo una secretaria podría perder tan sólo uno o dos minutos para encontrar el archivo de uno de los clientes de la compañía para la cual trabaja, esto, asumiendo que los archivos estén perfectamente ordenados y catalogados.
ALGORITMO
La búsqueda binaria funciona en arreglos ordenados. Consiste en eliminar, tras cada comparación, la mitad de los elementos del arreglo en los que se efectúa la búsqueda, comienza por comparar el elemento del medio del arreglo con el valor buscado. Si el valor buscado es igual al elemento del medio, su posición en el arreglo es retornada. Si el valor buscado es menor o mayor que el elemento del medio, la búsqueda continurá en la primera o segunda mitad, respectivamente, dejando la otra mitad fuera de consideración; y si son iguales, se ha encontrado dicho valor buscado y se devuelve la posición y sale del bucle; pero si no es así seguirá buscando dicho valor dentro del bucle y hará las comparaciones necesarias hasta encontrar el valor buscado.
Ahora veremos el código implementado en C++:
using namespace std;
int main()
{
int n, i, A[30], num, primero, ultimo, medio;
cout<<"Ingrese un arreglo ordenado: ";
cout<<"Cuantos elementos te gustaria ingresar?: ";
cin>>n;
for (i=0; i>A[i];
{
cout<<"Ingrese el numero que desea buscar: ";
cin>>num;
}
primero=0;
ultimo=n-1;
meedio=(primero+ultimo)/2;
while (primero<=ultimo);
{
if (A[medio]< num);
{
primero=medio+1;
} else if (A[medio]== num)
{
cout<<" Se encontro la posición ";
cout<<medio+1;
break;
}
else {
ultimo = medio - 1;
}
medio = (primero+ultimo)/2;
}
if (primero>ultimo)
{
cout<<num<<" no se encontro";
}
return 0;
}
Como podemos ver en el código dentro del Main se inicializa las variables que vamos a utilizar:
int n, i, A [30], num, primero, ultimo, medio;
Luego también hacemos uso de una estructura repetitiva FOR, para ayudar con la estética del código, donde nos pide ingresar por consola los numero ordenados para el array.
En nuestro for inicializamos nuestra variable iterativa i en 0, esta se incrementará en 1 por cada iteración hasta que sea igual a número n, que es la cantidad de números que ingresamos.
Luego hacemos uso de una condicional y ciclo while que realizará la búsqueda binaria, con el algoritmo antes explicado, importante es que el array debe estar ordenado ascendentemente.
El algoritmo funciona de la siguiente manera
Se determinan un índice primero=0 y un índice último=n-1, respectivamente.
Se determina un índice central, medio = (primero + último) /2.
Evaluamos si A[medio] es igual a la clave de búsqueda, si es igual ya encontramos la clave y devolvemos medio.
Si son distintos, evaluamos si A[medio] es mayor o menor que la clave, como el arreglo está ordenado al hacer esto ya podemos descartar una mitad del arreglo asegurándonos que en esa mitad no está la clave que buscamos.
En el momento de encontrar el dato, el programa sale del ciclo. Y de acuerdo al código se mostrará un mensaje: “SE ENCONTRÓ EL ELEMENTO EN LA POSICIÓN” y cuando sale del ciclo while habrá otro mensaje: “NO SE ENCONTRÓ”, el cual habla que el elemento no existe en el arreglo.
Para lograr entenderlo mejor, lo explicaremos con un ejemplo:
Por ejemplo, para buscar el elemento 3 en el array {1,2,3,4,5,6,7,8,9} se realizarán los siguientes pasos:
Se toma el elemento central y se divide el array en dos:
{1,2,3,4}-5-{6,7,8,9}
Como el elemento buscado (3) es menor que el central (5), debe estar en el primer subarray:
{1,2,3,4}
Se vuelve a dividir el array en dos:
{1}-2-{3,4}
Como el elemento buscado es mayor que el central, debe estar en el segundo subarray:
{3,4}
Se vuelve a dividir en dos:
{}-3-{4}
Como el elemento buscado coincide con el central, lo hemos encontrado.
Y bien de esta manera es como podemos implementar la búsqueda binaria, en simples pasos. Recuerda que este programa está desarrollado en C++, pero puede ser adaptado a cualquier otro lenguaje de programación; además de que le puedes agregar el método de ordenación, de tu preferencia. No olviden compartir con sus amigos y dejarnos sus dudas y opiniones en la caja de comentarios. Muchas gracias, ¡Hasta la próxima!