Antes de iniciar con la explicación hagamos un ejercicio mental, imaginemos que un amigo desea que adivinemos un número que tiene en un papel anotado y que solo él conoce, antes que empecemos nos advierte que el número está comprendido del 0 al 100, y por último por cada intento que hagamos el nos dirá si el número es mayor, menor o igual al número que tiene anotado en el papel.
Digamos que el número secreto a adivinar es el 81.
Bueno si eres sistemático empezaras intentando con el 50.
[1,2,3,.......,58,59,50,51,52,.......,98,99,100]
Tu amigo te dirá que el número que deseas adivinar es mayor que 50.
A éste punto ya debes deducir que el número está entre el 51 y el 100.
Observa como ya no tienes que gastar intentos con los números comprendidos de 0 a 50.
Ahora intentemos con el 75.
[51,52,53,.......,73,74,75,76,77,.......,98,99,100]
Tu amigo te dirá que el número que deseas adivinar es mayor que el 75.
A éste punto ya debes deducir que el número está entre el 76 y el 100.
Observa como ya no tienes que gastar intentos con los números comprendidos de 0 a 75.
Ahora intentemos con el 87.
[76,77,78,.......,85,86,87,88,89,.......,98,99,100]
Tu amigo te dirá que el número que deseas adivinar es menor que el 87.
A éste punto ya debes deducir que el número está entre el 76 y el 86.
Observa como ya no tienes que gastar intentos con los números comprendidos de 0 a 75 y 87 a 100.
Ahora intentemos con el 81.
[76,77,78,79,80,81,82,83,84,85,86]
Tu amigo te dirá que has acertado.
Si te has fijado, la técnica para adivinar el número es dividiendo el rango en dos partes, si el número a adivinar es mayor tomamos el rango que nos ha quedado a la derecha sino si el número a adivinar es menor tomamos el rango que nos ha quedado a la izquierda sino si el número es igual al número a adivinar, bingo hemos adivinado; si la primera vez no adivinamos el número realizamos los pasos anteriores nuevamente hasta que adivinemos (asumiendo que el número a adivinar existe).
La técnica anteriormente descrita es análoga a la técnica para la búsqueda binaria.
Como podemos observar y asumiendo la analogía, uno de los requisitos para el algoritmo de búsqueda binaria es que los datos esten previamente ordenados.
Este algoritmo se utiliza cuando el vector en el que queremos determinar la existencia de un elemento está previamente ordenado. El algoritmo reduce el tiempo de búsqueda considerablemente, ya que disminuye exponencialmente el número de iteraciones necesarias (wikipedia).
Para implementar este algoritmo se compara el elemento a buscar con un elemento cualquiera del array (normalmente el elemento central): si el valor de éste es mayor que el del elemento buscado se repite el procedimiento en la parte del array que va desde el inicio de éste hasta el elemento tomado, en caso contrario se toma la parte del array que va desde el elemento tomado hasta el final. De esta manera obtenemos intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible. Si el elemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra en todo el array (wikipedia).
He aquí el código que les ofrezco.
class BusquedaBinaria{
/**
* Busca un valor numerico dentro de un arreglo numerico...
* previamente ordenado usando el metodo de busqueda binaria
*
* @param arreglo con los elementos; dato a buscar
* @return posicion del elemento buscado, en caso de no existir retorna -1
*/
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;
}
public static void main(String []args){
int[]vector ={1,4,7,8,9,14,23,47,56,60,61,63,65,66,68,69,70,73,76,77,79,80,82};
int valorBuscado = 70;
System.out.println(busquedaBinaria(vector,valorBuscado));
}
}
