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í:

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:

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:

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í:

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 🙂