Introducción

Hoy veremos cómo implementar el algoritmo de búsqueda binaria en el lenguaje de programación Java. Este algoritmo funcionará  con números; y más tarde con cadenas. Veamos lo que haremos:

• Escribir una función que busque de forma binaria en arreglos de números usando recursividad o recursión
• Implementar el algoritmo de búsqueda binaria secuencial (con ciclos, en este caso while) en arreglos de números.

Aquí dejo una imagen del código para adornar el post. No te preocupes, podrás copiarlo como texto más abajo, esto es meramente ilustrativo.

Si quieres tomarle fotos a tu código, prueba Polacode; una extensión para VSCode.

Más tarde traeré la implementación para la búsqueda binaria en cadenas o strings.

Lecturas recomendadas

Esta misma implementación está en:

• PHP
• JavaScript
• Python

Para obtener el elemento del medio…

Para saber cuál elemento está a la mitad sumamos los límites, los dividimos entre 2 y redondeamos hacia abajo. Por ejemplo, si nuestro arreglo es de 5 elementos: izquierda es 0, derecha es 4 (recordemos que los índices empiezan en 0), al sumarlos da 4. Los dividimos entre 2 y da 2, finalmente al redondearlo hacia abajo sigue siendo 2.

Esa es exactamente la mitad del arreglo, la posición 2. Y si el elemento que buscamos no está ahí, nos vamos a la izquierda o derecha.

El redondeo es necesario cuando tenemos un arreglo cuya longitud es par. Por ejemplo, si tenemos un arreglo de 6 entonces: izquierda es 0, derecha es 5.

Al sumarlos da 5, dividimos y es 2.5 pero no existe la posición o índice 2.5; por eso es necesario redondear. Al redondear hacia abajo se convierte en 2, y si bien esa no es justamente la mitad, el algoritmo no falla, pues se irá a la izquierda o derecha de ese valor según sea el caso.

Por cierto, para redondear hacia abajo usamos Math.floor.

Búsqueda binaria recursiva en Java: arreglo numérico

Primero veamos el enfoque que usa recursión o recursividad. Es cuando la función se llama a sí misma; la condición de salida se pone al regresar un valor que no sea una llamada a la función. Por ejemplo, regresando -1 con return -1; o regresando el índice con return indiceDelElementoDelMedio;

Todo está en una función que recibe el arreglo, la búsqueda, el límite inferior (izquierda) y el superior (derecha). Queda así:

/**
        Algoritmo de búsqueda binaria recursiva en Java
        @author parzibyte
        @web parzibyte.me/blog
    */
    public static int busquedaBinariaRecursiva(int[] arreglo, int busqueda, int izquierda, int derecha){
 
        // Si izquierda es mayor que derecha significa que no encontramos nada
        if(izquierda > derecha){
            return -1;
        }
 
        // Calculamos las mitades...
        int indiceDelElementoDelMedio = (int) Math.floor((izquierda + derecha) / 2);
        int elementoDelMedio = arreglo[indiceDelElementoDelMedio];
 
        // Ver si está en la mitad
        if(elementoDelMedio == busqueda){
            return indiceDelElementoDelMedio;
        }
        // Si no, entonces vemos si está a la izquierda o derecha
 
        if(busqueda < elementoDelMedio){
            derecha = indiceDelElementoDelMedio - 1;
            return busquedaBinariaRecursiva(arreglo, busqueda, izquierda, derecha);
        }else{
            izquierda = indiceDelElementoDelMedio + 1;
            return busquedaBinariaRecursiva(arreglo, busqueda, izquierda, derecha);
        }
    }

Explicando un poco, obtenemos el elemento que está en la mitad del arreglo. Si lo que buscamos está en medio, entonces regresamos su índice. Si no, entonces vemos si está hacia la izquierda o derecha; pues nuestro arreglo está ordenado (eso es un requisito de la búsqueda binaria).

La parte en donde se parte el arreglo es cuando establecemos a derecha en indiceDelelementoDelMedio - 1 o a izquierda en indiceDelElementoDelMedio + 1.

Es una función estática porque la he puesto dentro de la clase principal, y recordemos que una función de este tipo nos permite llamarla sin instanciar un objeto de su clase.

En resumen, si lo implementas en otro lugar en donde sí haces una nueva instancia, simplemente quita el static.

Para llamarlo dentro de la misma clase usé esto:

// Arreglo para probar
int[] arreglo = {5, 7, 11, 20, 21, 25, 80, 85, 90, 95, 97, 98, 115, 500, 510, 512, 1024};
 
int busqueda = 500;
 
int indiceDelElementoBuscado = busquedaBinariaRecursiva(arreglo, busqueda, 0, arreglo.length - 1);
System.out.println("[Recursivo] -- El elemento buscado (" + String.valueOf(busqueda) + ") se encuentra en el index " + indiceDelElementoBuscado);

De esta forma, en la consola se imprime algo así:

[Recursivo] — El elemento buscado (500) se encuentra en el index 13

Y listo, así queda la implementación. Como vemos, la primera vez los límites son 0 y N – 1 en donde N es la longitud de nuestro arreglo.

Búsqueda binaria secuencial en Java con arreglo numérico

Veamos la búsqueda binaria pero ahora hecha con un ciclo o de forma secuencial, sin usar recursividad. Es casi lo mismo, la condición se salida es cuando izquierda es mayor que derecha.

Dentro del ciclo únicamente movemos los límites; comprobamos si está en el medio y si no entonces seguimos iterando hasta que la condición de salida se alcance.

Si terminamos el ciclo y no encontramos nada, significa que no encontramos la búsqueda, y regresamos -1.

He aquí la función:

/**
    Algoritmo de búsqueda binaria secuencial en Java
    @author parzibyte
    @web parzibyte.me/blog
*/
public static int busquedaBinariaConWhile(int[] arreglo, int busqueda){
    int izquierda = 0, derecha = arreglo.length - 1;
 
    while(izquierda <= derecha){
        // Calculamos las mitades...
        int indiceDelElementoDelMedio = (int) Math.floor((izquierda + derecha) / 2);
        int elementoDelMedio = arreglo[indiceDelElementoDelMedio];
 
        // Ver si está en la mitad y romper aquí el ciclo
        if(elementoDelMedio == busqueda){
            return indiceDelElementoDelMedio;
        }
        // Si no, entonces vemos si está a la izquierda o derecha
 
        if(busqueda < elementoDelMedio){
            derecha = indiceDelElementoDelMedio - 1;
        }else{
            izquierda = indiceDelElementoDelMedio + 1;
        }
    }
    // Si no se rompió el ciclo ni se regresó el índice, entonces el elemento no existe
    return -1;
}

La función únicamente recibe 2 argumentos: el arreglo y la búsqueda. Si bien también son necesarios los límites, los mismos son calculados internamente al inicio; antes del ciclo.

Podemos probarla así:

// Arreglo para probar
int[] arreglo = {5, 7, 11, 20, 21, 25, 80, 85, 90, 95, 97, 98, 115, 500, 510, 512, 1024};

int busqueda = 500;
// Ahora con la que usa el ciclo while
int indiceDelElementoBuscado = busquedaBinariaConWhile(arreglo, busqueda);
System.out.println("[Con ciclo While] -- El elemento buscado (" + String.valueOf(busqueda) + ") se encuentra en el index " + indiceDelElementoBuscado);

Si lo ejecutamos, sale:

[Con ciclo While] — El elemento buscado (500) se encuentra en el index 13

Conclusión

Listo, hemos terminado. Muy pronto escribiré el post explicando la búsqueda binaria pero con cadenas, que es casi igual pero supongo que usando algo equivalente a localeCompare de JavaScript.

Actualización: aquí está el tutorial para la búsqueda binaria en Strings usando Java.

Nos vemos luego 🙂