Busqueda Binaria

Busqueda Binaria
Este algoritmo permite buscar de una manera más eficiente un dato dentro de un arreglo, para hacer esto se determina el elemento central del arreglo y se compara con el valor que seesta buscando, si coincide termina la busqueda y en caso de no ser asi se determina si el dato es mayor o menor que el elemento central, de esta forma se elimina una mitad del arreglo junto con elelemento central para repetir el proceso hasta encontrarlo o tener solo un elemento en el arreglo. Para poder aplicar este algorimo se requiere que el arreglo este ordenado. Su implementación es lasiguiente:
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:
intvector[10] =
{2,4,6,8,10,12,14,16,18,20};
La clave que queremos buscar es 6. El algoritmo funciona de la siguien manera
1. Se determinan un indice arriba y un indice abajo, Iarriba=0 e Iabajo=9respectivamente.
2. Se determina un indice central, Icentro = (Iarriba + Iabajo)/2, en este caso quedaría Icentro = 4.
3. Evaluamos si vector[Icentro] es igual a la clave de busqueda, si es igual yaencontramos la clave y devolvemos Icentro.
4. Si son distintos, evaluamos si vector[Icentro] es mayor o menos que la clave, como el arreglo está ordenado al hacer esto ya podemos descartar una mitad delarreglo asegurandonos que en esa mitad no está la clave que buscamos. En nuestro caso vector[Icentro] = 4 < 6, entonces la parte del arreglo vector[0...4] ya puede descartarse.
5. Reasignamos Iarribao Iabajo para obtener la nueva parte del arreglo en donde queremos buscar. Iarriba, queda igual ya que sigue siendo el tope. Iabajo lo tenemos subir hasta 5, entonces quedaria Iarriba = 9, Iabajo = 5.Y volvemos al paso 2.
Si la clave no fuese encontrada en algun momento Iabajo > Iarriba, con un while vamos a controlar esta condición para salir del ciclo en tal caso y devolver -1 (clave no...