martes, 29 de noviembre de 2011

Busqueda Binaria

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).

OPERACIONES.-Todas las operaciones realizadas sobre árboles binarios de búsqueda están basadas en la comparación de los elementos o clave de los mismos, por lo que es necesaria una subrutina, que puede estar predefinida en el lenguaje de programación, que los compare y pueda establecer una relación de orden entre ellos, es decir, que dados dos elementos sea capaz de reconocer cual es mayor y cual menor. Se habla de clave de un elemento porque en la mayoría de los casos el contenido de los nodos será otro tipo de estructura y es necesario que la comparación se haga sobre algún campo al que se denomina clave.
 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.

Este método permite buscar un valor en una matriz que se esta ordenando ascendentemente utilizando el algoritmo de búsqueda binaria. Se trata de un algoritmo muy eficiente en cuanto el tiempo requerido para realizar una búsqueda es muy pequeño. La sintaxis expresada de forma genérica para realizar este método es la siguiente:
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
  1. Se determinan un índice arriba y un índice abajo, Iarriba=0 e Iabajo=10 respectivamente.
  2. Se determina un índice central, Icentro = (Iarriba + Iabajo)/2, en este caso quedaría Icentro = 5.
  3. Evaluamos si vector[Icentro] es igual a la clave de búsqueda, si es igual ya encontramos la clave y devolvemos Icentro.
  4. 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.
  5. 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;
}
video de busqueda binaria




 


 

No hay comentarios:

Publicar un comentario en la entrada