Búsqueda binaria con Java

Una búsqueda binaria con Java es aquella que permite localizar un elemento dentro de una colección, en nuestro caso un array, comparando los valores que hay dentro del array.

El proceso que se realiza en una búsqueda binaria sería el siguiente:

1. En primer lugar es ordenar los elementos, ya que a partir de ese momento buscará por ubicación dentro de la lista de elementos.
2. Lo siguiente que hace es validar si el número que sea la mitad del array coincide con el número buscado.
3. En el caso que no coincida realiza la siguiente comparación. Si el elemento que buscamos es menor al elemento que está en medio del array se queda con la parte izquierda del array, si el elemento que buscamos es mayor que el elemento que está en medio del array se queda con la parte derecha del array.
4. Elige una de las dos partes y vuelve a realizar lo indicado en el punto 2. Así hasta que encuentre el número buscado o bien retorne indicando que no ha encontrado elemento.

Implementación

Si vamos a realizar una búsqueda binaria en Java lo primero que tendremos que tener es un array y el número que queremos encontrar.

int[] numeros = {3, 7, 1, 9, 5, 2, 8, 4, 6};
int numeroBuscado = 5;

Lo siguiente será ordenar el array, ya que no sabremos si por defecto está ordenado. Para ello vamos a utilizar el método Arrays.sort() el cual recibirá el array como parámetro.

Arrays.sort(numeros);

Ahora podríamos codificarnos el algoritmo de búsqueda binaria con Java (que lo haremos en otro ejemplo), pero en este caso vamos a utilizar el método Arrays.binarySearch(array, numero) que realiza la búsqueda por nosotros.

Este método recibe por un lado el array ordenado con los números y por otro el número que estamos buscando. El caso de encontrar el número nos devolverá un valor entero con la posición que ocupa dentro del array el número buscado, si no se encuentra dentro del array devolverá un número negativo.

Así utilizaremos la siguiente estructura para buscarlo:

int posicion = Arrays.binarySearch(numeros, numeroBuscado);

if (posicion >= 0) {
    System.out.println("El número " + numeroBuscado + " está en la posición " + posicion);
} else {
    System.out.println("El número " + numeroBuscado + " no se encuentra en el array");
}

De esta forma tan sencilla tendremos una búsqueda binaria con Java.