CONCEPTO1.- Es un metodo que permite buscar un valor en una matriz que se esta ordenando ascendentemente utilizando el algoritmo de busqueda binaria. Es un algoritmo muy eficiente ya que requiere de poco tiempo para realizar una busqueda CONCEPTO2.- La búsqueda binaria consiste en dividir el array por su elemento medio en dos subarrays más pequeños, y comparar el elemento con el del centro. Si coinciden, la búsqueda se termina. Si el elemento es menor, debe estar (si está) en el primer subarray, y si es mayor está en el segundo.
CARACTERISTICAS.- Uno de los algoritmos de búsqueda más eficiente que existe en la estructura de datos es la búsqueda binaria, las características para poder implementar este algoritmo son las siguientes:- Los datos deben estar contenido en un estructura de datos tipo vector
- Los datos del vector deben estar ordenados
Una vez que se cuenten son las características descritas, se divide el vector para poder conocer la posición central y se verifica si es el dato que se esta buscando (lineas 9-12), si es el dato que se busca regresa la posición (índice del vector), en caso de que no sea el dato que buscamos se verifica si es mayor o menor que la posición central y se vuelve a redefinir la posición final o inicial según cumpla la condición (lineas 14-18).
Por ejemplo, para buscar el elemento 3 en el array {1,2,3,4,5,6,7,8,9} se realizarían 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.
Int BinarySearch ([ ] m. tipo clave)
La búsqueda binaria sólo se puede implementar si el arreglo está ordenado. La idea consiste en ir dividiendo el arreglo en mitades. Por ejemplo supongamos que tenemos este vector:
int vector[10] = {2,4,6,8,10,12,14,16,18,20};
La clave que queremos buscar es 6. El algoritmo funciona de la siguiente manera
- Se determinan un índice arriba y un índice abajo, Iarriba=0 e Iabajo=10 respectivamente.
- Se determina un índice central, Icentro = (Iarriba + Iabajo)/2, en este caso quedaría Icentro = 5.
- Evaluamos si vector[Icentro] es igual a la clave de búsqueda, si es igual ya encontramos la clave y devolvemos Icentro.
- Si son distintos, evaluamos si vector[Icentro] 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 nuestro caso vector[Icentro] = 5 < 6, entonces la parte del arreglo vector[0…5] ya puede descartarse.
- Reasignamos Iarriba o Iabajo para obtener la nueva parte del arreglo en donde queremos buscar. Iarriba, queda igual ya que sigue siendo el tope. Iabajo lo tenemos que subir hasta 6, entonces quedaría Iarriba = 10, Iabajo = 6. Y volvemos al paso 2.
PROGRAMA.-
//Busqueda binaria
//en un arreglo.
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
void mostrarArreglo(const int[], int); //prototipo de funcion que
recibe un arreglo constante
int busquedaBinaria(const int[], int, int); //arreglo, tamano, clave
void ordenarArreglo(int[], int); //prototipo que modifica y ordena el
arreglo
void intercambiar(int&, int&); //prototipo, intercambia
los valores de dos elementos
int main()
{
int clave =0;
const int tamano = 15;
int arreglo[tamano] = {25,17,13,16,41,32,12,115,95,84,54,63,78…
//ordenamos el arreglo para que funcione la busquedaBinaria
ordenarArreglo(arreglo,tamano);
cout << "Elementos del arreglo: " << endl;
mostrarArreglo(arreglo,tamano);
cout << "Indique un valor a buscar y se le devolvera el indice: " << endl;
cin >> clave;
cout<< "Su valor se encuentra en arreglo["<<busquedaBinaria(arreglo,taman… << endl;
cout << "Fin del programa :)" << endl;
return 0;
}//fin de main
void mostrarArreglo(const int arreglo[], int tamano)
{
for (int i = 0 ; i < tamano ; i++)
cout << "arreglo[" << i << "]=" << arreglo[i] << endl;
}
int busquedaBinaria(const int arreglo[], int tamano, int clave)
{
int Iarriba = tamano-1;
int Iabajo = 0;
int Icentro;
while (Iabajo <= Iarriba)
{
Icentro = (Iarriba + Iabajo)/2;
if (arreglo[Icentro] == clave)
return Icentro;
else
if (clave < arreglo[Icentro])
Iarriba=Icentro-1;
else
Iabajo=Icentro+1;
}
return -1;
}
void ordenarArreglo(int arreglo[], int tamano)
{
for (int i = 0; i< tamano -1 ; i++)
for (int j = 0; j< tamano -1 ; j++)
if (arreglo[j] > arreglo[j+1])
intercambiar(arreglo[j],arreglo[j+1]);
}
void intercambiar(int &a, int &b)
{
int tmp = b;
b = a;
a = tmp;
}
//en un arreglo.
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
void mostrarArreglo(const int[], int); //prototipo de funcion que
recibe un arreglo constante
int busquedaBinaria(const int[], int, int); //arreglo, tamano, clave
void ordenarArreglo(int[], int); //prototipo que modifica y ordena el
arreglo
void intercambiar(int&, int&); //prototipo, intercambia
los valores de dos elementos
int main()
{
int clave =0;
const int tamano = 15;
int arreglo[tamano] = {25,17,13,16,41,32,12,115,95,84,54,63,78…
//ordenamos el arreglo para que funcione la busquedaBinaria
ordenarArreglo(arreglo,tamano);
cout << "Elementos del arreglo: " << endl;
mostrarArreglo(arreglo,tamano);
cout << "Indique un valor a buscar y se le devolvera el indice: " << endl;
cin >> clave;
cout<< "Su valor se encuentra en arreglo["<<busquedaBinaria(arreglo,taman… << endl;
cout << "Fin del programa :)" << endl;
return 0;
}//fin de main
void mostrarArreglo(const int arreglo[], int tamano)
{
for (int i = 0 ; i < tamano ; i++)
cout << "arreglo[" << i << "]=" << arreglo[i] << endl;
}
int busquedaBinaria(const int arreglo[], int tamano, int clave)
{
int Iarriba = tamano-1;
int Iabajo = 0;
int Icentro;
while (Iabajo <= Iarriba)
{
Icentro = (Iarriba + Iabajo)/2;
if (arreglo[Icentro] == clave)
return Icentro;
else
if (clave < arreglo[Icentro])
Iarriba=Icentro-1;
else
Iabajo=Icentro+1;
}
return -1;
}
void ordenarArreglo(int arreglo[], int tamano)
{
for (int i = 0; i< tamano -1 ; i++)
for (int j = 0; j< tamano -1 ; j++)
if (arreglo[j] > arreglo[j+1])
intercambiar(arreglo[j],arreglo[j+1]);
}
void intercambiar(int &a, int &b)
{
int tmp = b;
b = a;
a = tmp;
}
video de busqueda binaria
No hay comentarios:
Publicar un comentario