6.2 BUSQUE BINARIA

6.2 Búsqueda Binaria

Este método requiere que los valores en el arreglo estén ordenados.

La búsqueda binaria consiste en dividir el intervalo de búsqueda en dos partes, comparando el elemento buscado con el que ocupa la posición central en el arreglo. Para el caso de que no fueran iguales se redefinen los extremos del intervalo , según el elemento central sea mayor o menor que el elemento buscado, disminuyendo de esta forma el espacio de búsqueda. El proceso concluye cuando el elemento es encontrado, o cuando el intervalo de búsqueda termina.

Ejemplo de la vida cotidiana

*”Una búsqueda binaria típica es la búsqueda de una palabra en un diccionario. Dada la palabra, se abre el libro cerca del principio, del centro o del final dependiendo de la primera letra de la palabra que busca. Se puede tener suerte y acertar con la pagina correcta pero, normalmente no será así y el lector se mueve a la pagina anterior o posterior del libro. El proceso continua asta que se encuentre la pagina buscada o hasta que se descubre que la palabra no esta en la lista”

Ejemplo en un vector








Numero a buscar : 76
índice medio= (índice inicial+ índice final)/2

índice medio= (0+14)/2= 7
47=76 false
47<76 true
(índice inicial=8, índice final= 14)

medio=(2+14)/2= 11
77=76 false
77<76 false
77>76 true
(índice inicial= 8, índice final=11)

medio=(8+11)/2= 9
64=76 false
64<76 true
(índice inicial=9, índice final=11)

medio=(9+11)/2= 10

76=76 true

Implementacion en Java

public static int busquedaBinaria(int  vector[], int dato){

  int n = vector.length;

  int centro,inf=0,sup=n-1;

   while(inf<=sup){

     centro=(sup+inf)/2;

     if(vector[centro]==dato) return centro;

     else if(dato < vector [centro] ){

        sup=centro-1;

     }

     else {

       inf=centro+1;

     }

   }

   return -1;

 }

Ventajas y desventajas

Ventajas

•  Es notablemente mas rápido que el método secuencial.
• Es muy útil en archivos extensos y grandes cantidades de datos.
•  El código del procedimiento de esta búsqueda es corto en comparación con las demás técnicas de búsqueda

Desventajas

• El arreglo o archivo tiene que estar ordenado.
• No revisa todos los elementos del arreglo