En otro artículo ya vimos cómo podemos realizar una búsqueda binaria con Java mediante el método .binarySearch() la cual utiliza el algoritmo de búsqueda binaria para poder localizar un número dentro de un array. En este caso vamos a ver cómo podemos implementar una búsqueda binaria con Java de forma directa.
Lo primero será partir de un array de números sobre los que vamos a realizar la búsqueda, al igual que declarar una variable con el número que queremos buscar. Algo sencillo para empezar:
int[] numeros = {12,45,67,27,89,84,65,21,44};
int numberToSearch = 12;
Lo siguiente que haremos será ordenar el Array, ya que sabemos que la premisa para poder implementar una búsqueda binaria con Java es que el array se encuentre ordenado.
Ahora vamos al meollo del problema que es la implementación de un método que nos realice la búsqueda binaria. El método recibirá como parámetros el array con los números y el número a buscar.
public static boolean binarySearch(int[] numbers, int numberToSearch) { ... }
La idea de la búsqueda binaria es encontrar el número pensando que el número se encuentra en el centro del array, así que lo primero que hace es mirar si el número buscado coincide con el que está a la mitad.
int size = numbers.length; // Número de elementos
int middle = size/2; // Mitad del array
if (numbers[middle] == numberToSearch)
return true;
En el caso que el número coincida devolveremos un valor de true. Si con coincide podremos tomar dos caminos:
a) Si el número buscado es mayor que el número que se encuentra en la mitad, lanzaremos la búsqueda sobre la mitad superior del array invocando de forma recursiva al mismo método.
b) Si el número buscado es menor que el número que se encuentra en la mitad, lanzaremos la búsqueda sobre la mitad inferior del array, nuevamente invocándolo de forma recursiva al método.
else if (numbers[middle] > numberToSearch) return binarySearch(Arrays.copyOfRange(numbers,0,middle),numberToSearch); else return binarySearch(Arrays.copyOfRange(numbers,middle+1,size),numberToSearch);
Hay que notar que utilizaremos el método Arrays.copyOfRange() para obtener una parte del array o la otra.
Al final, si el tamaño del array que recibe el método es igual a 1 y no coincide con el número buscado significará que el número no se encuentra dentro del array.
if (numbers[middle] == numberToSearch) return true; else if (size == 1) return false;
El método binarySearch que hemos implementado quedará de la siguiente forma:
public static boolean binarySearch(int[] numbers, int numberToSearch) {
int size = numbers.length; // Número de elementos
int middle = size/2; // Mitad del array
System.out.println("Size: " + size);
System.out.println("Middle: " + middle);
System.out.println("Array: " + Arrays.toString(numbers));
if (numbers[middle] == numberToSearch)
return true;
else if (size == 1)
return false;
else if (numbers[middle] > numberToSearch)
return binarySearch(Arrays.copyOfRange(numbers,0,middle),numberToSearch);
else
return binarySearch(Arrays.copyOfRange(numbers,middle+1,size),numberToSearch);
}
Hemos añadido unas salidas por consola para que se vea cómo va funcionando el método al implementar una búsqueda binaria con Java.
¿Conoces más métodos de búsqueda? Puedes compartirlos en los comentarios.
