Introducción

Hoy veremos cómo usar e implementar el algoritmo de búsqueda binaria en arreglos usando JavaScript. Veremos tanto la forma que usa recursividad (también llamada recursión o de forma recursiva) así como la forma que utiliza una sentencia de control del ciclo while.

Este algoritmo de búsqueda binaria en JavaScript funciona en arreglos de strings y de números, en otras palabras funciona en arreglos de tipo int y de tipo string, ya que JavaScript sí compara a las cadenas usando los símbolos de <strong>></strong> mayor qué y <strong><</strong> menor qué.

Vamos a ver cómo implementar este algoritmo de búsqueda binaria que tiene el enfoque de divide y vencerás, usando el lenguaje de programación JavaScript que se puede ejecutar en el navegador web o en Node

Lecturas recomendadas

• Mira cómo implementar la búsqueda binaria en PHP
• Aquí encontrarás más tutoriales de JavaScript
• Recomiendo leer qué es const, y el uso de las funciones flecha en JS
• El arreglo debe estar ordenado previamente, pásate por este post para saber cómo ordenar arreglos en JavaScript

Búsqueda binaria en arreglo de JavaScript usando recursividad

Primero veamos el enfoque que hace que busquemos en un arreglo usando recursión o recursividad. Ya lo dije hace un momento, esta función buscará tanto en arreglos o arrays de cadenas así como en los de enteros o arreglos numéricos.

Es una función a la que le pasamos el límite inferior, el superior, el arreglo y la búsqueda. No en ese orden, el orden se puede ver en la declaración de la misma.

/**
 * 
 * Implementación del algoritmo de búsqueda binaria recursiva en un arreglo
 * usando JavaScript
 * 
 * Funciona con arreglos de números así como de cadenas
 * 
 * Autor: parzibyte
 * Web: parzibyte.me/blog
 */
 
 
const busquedaBinariaRecursiva = (arreglo, busqueda, izquierda, derecha) => {
    /*
        Si el arreglo ya no puede ser dividodo
        entonces significa que no encontramos el elemento
        y devolvemos -1
    */
    if (izquierda > derecha) return -1;
    /*
        Obtenemos el elemento medio del arreglo; 
        para ello sumamos los límites, los dividimos entre 2 y
        al número resultante lo redondeamos hacia abajo
 
        Con eso tenemos el índice, y para sacar el valor simplemente
        accedemos a él usando arreglo[indice]
 
    */
    let indiceDelElementoQueEstaEnLaMitad = Math.floor((derecha + izquierda) / 2);
    let valorQueEstaEnLaMitad = arreglo[indiceDelElementoQueEstaEnLaMitad];
 
    /*
        Probar si el elemento que buscamos está en medio
    */
    if (busqueda === valorQueEstaEnLaMitad) {
        return indiceDelElementoQueEstaEnLaMitad;
    } else {
        /*
        Si no, comprobamos si la búsqueda está hacia la derecha o hacia la izquierda
        ¿y cómo sabemos eso? debido a que el arreglo está ordenado, si la búsqueda
        es mayor que el elemento del medio, puede que lo que busquemos esté hacia la derecha
 
        Si la búsqueda es menor que el elemento del medio, puede que lo que busquemos esté hacia la izquierda
        */
        if (busqueda > valorQueEstaEnLaMitad) {
            // Si el valor está hacia la derecha, entonces comenzamos desde la derecha del punto medio hasta la derecha
            izquierda = indiceDelElementoQueEstaEnLaMitad + 1
            // derecha se queda intacta
            return busquedaBinariaRecursiva(arreglo, busqueda, izquierda, derecha);
        } else {
            // Si  el valor está hacia la izquierda, entonces comenzamos desde la izquierda del punto medio, hasta la izquierda
            derecha = indiceDelElementoQueEstaEnLaMitad - 1
            // izquierda se queda intacta
            return busquedaBinariaRecursiva(arreglo, busqueda, izquierda, derecha);
        }
    }
}

Esta función devuelve el índice del elemento que buscamos, y el valor -1 si no encuentra nada. El orden de los argumentos que recibe es:

1. El arreglo
2. La búsqueda
3. El límite inferior o la izquierda
4. El límite superior o la derecha

Probar algoritmo

Para probar esta función aquí dejo un ejemplo de código:

// Probar algoritmo
const arreglo = [1, 2, 5, 8, 10, 11, 11, 16, 20, 80, 500, 500, 1000, 1002, 5000],
    busqueda = 80;
 
const indice = busquedaBinariaRecursiva(arreglo, busqueda, 0, arreglo.length - 1);
console.log("El valor %s está en el índice %d", busqueda, indice);

Como vemos, la primera vez le pasamos los límites en 0 y en N, en donde N es la longitud del arreglo -1, esto es su último índice. De ahí, internamente se irá partiendo el arreglo.

La salida es: El valor 80 está en el índice 9

Por cierto, ya dije que funciona con cadenas y números. Eso sí, si buscamos una cadena el arreglo debe ser de strings, y si el arreglo es de enteros o flotantes, pues debemos buscar uno de ellos. Una búsqueda en un arreglo mixto puede traer resultados inesperados.

Búsqueda binaria en JavaScript usando el ciclo while

Si no nos gusta usar la recursión y preferimos usar un ciclo, podemos hacerlo. En este caso la función casi no cambia, pues nos metemos a un ciclo que se rompe cuando el elemento se encuentra o el límite inferior es mayor al superior.

El ciclo o sentencia de control que usamos es while.

Aquí la función:

/**
 * 
 * Implementación del algoritmo de búsqueda binaria secuencial en un arreglo
 * usando JavaScript
 * 
 * Funciona con arreglos de números así como de cadenas
 * 
 * Autor: parzibyte
 * Web: parzibyte.me/blog
 */
 
const busquedaBinaria = (arreglo, busqueda) => {
    let izquierda = 0, derecha = arreglo.length - 1;
    while (derecha >= izquierda) {
        let indiceDelElementoQueEstaEnLaMitad = Math.floor((derecha + izquierda) / 2);
        let valorQueEstaEnLaMitad = arreglo[indiceDelElementoQueEstaEnLaMitad];
 
        /*
            Probar si el elemento que buscamos está en medio
        */
        if (busqueda === valorQueEstaEnLaMitad) {
            return indiceDelElementoQueEstaEnLaMitad;
        } else {
            /*
            Si no, comprobamos si la búsqueda está hacia la derecha o hacia la izquierda
            ¿y cómo sabemos eso? debido a que el arreglo está ordenado, si la búsqueda
            es mayor que el elemento del medio, puede que lo que busquemos esté hacia la derecha
    
            Si la búsqueda es menor que el elemento del medio, puede que lo que busquemos esté hacia la izquierda
            */
            if (busqueda > valorQueEstaEnLaMitad) {
                // Si el valor está hacia la derecha, entonces comenzamos desde la derecha del punto medio hasta la derecha
                izquierda = indiceDelElementoQueEstaEnLaMitad + 1
                // derecha se queda intacta
            } else {
                // Si  el valor está hacia la izquierda, entonces comenzamos desde la izquierda del punto medio, hasta la izquierda
                derecha = indiceDelElementoQueEstaEnLaMitad - 1
                // izquierda se queda intacta
            }
        }
        // El ciclo continúa, pero ya cambiamos izquierda o derecha según haya sido el caso
    }
    return -1;
}

Esta función recibe únicamente dos argumentos: el arreglo y la búsqueda. Ya que los límites o izquierdas y derechas son calculados internamente.

Devuelve igualmente -1 en caso de no encontrar el elemento, o un número indicando el índice del elemento que buscamos.

Llamada a la función

Si deseamos probar este algoritmo de búsqueda binaria en JS podemos emplear un código así:

// Probar el algoritmo
const arreglo = [1, 2, 5, 8, 10, 11, 11, 16, 20, 80, 500, 500, 1000, 1002, 5000],
    busqueda = 20;
const indice = busquedaBinaria(arreglo, busqueda);
console.log("El valor %s está en el índice %d", busqueda, indice);

La salida será: El valor 20 está en el índice 8

Y sí, sí funciona con cadenas y números.

Conclusión

De esta manera podemos implementar el algoritmo de la búsqueda binaria en arreglos de JavaScript. No importa si los arreglos son de enteros o de cadenas.

Este método es muy rápido, por cierto. Pues su complejidad es de O(log n) en el peor de los casos.