Implementar una búsqueda binaria con Java

18/Mar/2020 Java 1 Comentario
Programación en Java

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.

Vídeos sobre Java


Un comentario en “Implementar una búsqueda binaria con Java”

Víctor Cuervo

Yamil

¿No conlleva un uso muy alto de recursos hacer una y otra vez una copia del array? Pienso que es mas conveniente llevar un conteo de los mínimos y máximos, de esta forma nos quedaremos con la parte del array que nos interesa

¿Algo que nos quieras comentar?

Déjanos tu comentario, no te preocupes que tu email no será publicado

*

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.