] Búsqueda binaria
Para utilizar este algoritmo, el array debe estar ordenado. 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.
Ejemplos:
A) 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.
*Si al final de la búsqueda todavía no lo hemos encontrado, y el subarray a dividir está vacio {}, el elemento no se encuentra en el array. La implementación sería:
int desde,hasta,medio,elemento,posicion; // desde y
// hasta indican los límites del array que se está mirando.
int array[N];
// Dar valor a elemento.
for(desde=0,hasta=N-1;desde<=hasta {
if(desde==hasta) // si el array sólo tiene un elemento:
{
if(array[desde]==elemento) // si es la solución:
posición=desde; // darle el valor.
else // si no es el valor:
posición=?1; // no está en el array.
break; // Salir del bucle.
}
medio=(desde+hasta)/2; // Divide el array en dos.
if(array[medio]==elemento) // Si coincide con el central:
{
posición=medio; // ese es la solución
break; // y sale del bucle.
}
else if(array[medio]>elemento) // si es menor:
hasta=medio-1; // elige el array izquierda.
else // y si es mayor:
desde=medio+1; // elige el array de la derecha.
}
B) 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.
ANALISIS DE LA BUSQUEDA BINARIA:
La búsqueda binaria es un método eficiente siempre que el vector este ordenado.
En la práctica esto puede suceder, pero no siempre. Por esta razón la búsqueda binaria exige un ordenamiento previo del vector.
Para poder medir la velocidad de cálculo del algoritmo de búsqueda binaria se deberán obtener el número de comparaciones que realiza el algoritmo.
Consideremos un vector de siete elementos (n=7).El número 8(n+1) se debe dividir en tres mitades antes de que se alcance 1;es decir, se necesitan tres comparaciones.
1 2 3 4
5 6 7
El medio matemático de expresar estos números es:
3=log?(8)
En general, para n elementos es:
K=log?(n+1) ? K=número de comparaciones.
Si n+1 no es una potencia de 2 el valor del logaritmo se redondeara hasta el siguiente entero.
Por ejemplo:
Si n es 12, k será 4 ya que log?(13) (que está entre 3 y 4) se redondeara hasta 4(2?es 16).
Para poder efectuar una comparación entre el método de búsqueda binaria y búsqueda secuencial, realicemos los cálculos correspondientes para diferentes vectores de n.
n=100 En la búsqueda secuencial se necesitaran:
100+1
2
50 comparaciones.
En la búsqueda binaria:
log? (100)= 6.643856190=7
7 comparaciones.
n=1000000 En la búsqueda secuencial se necesitan:
1000000+1
2
500000 comparaciones.
En la búsqueda binaria:
log? (1000000)= 19.93156857=20
20 comparaciones.
El método mas eficiente de búsqueda en una tabla secuencial sin utilizar índices o tablas auxiliares es la búsqueda binaria. Para poder llevarse acabo esta, necesita tener el arreglo ordenado. Básicamente, el argumento se compara con la llave del elemento intermedio de la tabla. Si son iguales, la búsqueda termina exitosamente; en caso contrario, debe buscarse en la mitad superior o inferior en la tabla en una forma similar.
int Buscar( int num, int vect[]){
int num, izq,der, cen;
izq=0; der=n-1;
while( izq < = der ){
cen=( izq + der )/2;
if( vect[cen] = = num )
return cen;
if( num > vect[cen] )
izq=cen+1;
else
der=cen-1;
}
return (-1);
}
descarga
http://www.ziddu.com/download/7150546/BUsQUEDABINARIA.rar.html
Aca les dejo un ejmplo en c++
cpp
http://www.ziddu.com/download/7150547/BUSQUEDABINARIACPP.rar.html
Opciones
Post Relacionados
- metodos de busqueda y ordenamiento(shell,binaria,quicksort,)
- Aleacion Binaria - En la Senda del Metal (2005)
- programa para generar secuencia binaria en el puerto paralel
- programa para generar secuencia binaria en el puerto paralel
- programa para generar secuencia binaria en el puerto paralel
- Programar un juego para Windows con C++
- Como Programar en C/C++
- Aprendé a Programar páginas Web en HTML
- como programar en java -deitel quinta edicion
- Programar en C
Información del post
