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
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:
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.
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.
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.
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.
Hoy te voy a presentar un creador de credenciales que acabo de programar y que…
Ya te enseñé cómo convertir una aplicación web de Vue 3 en una PWA. Al…
En este artículo voy a documentar la arquitectura que yo utilizo al trabajar con WebAssembly…
En un artículo anterior te enseñé a crear un PWA. Al final, cualquier aplicación que…
Al usar Comlink para trabajar con los workers usando JavaScript me han aparecido algunos errores…
En este artículo te voy a enseñar cómo usar un "top level await" esperando a…
Esta web usa cookies.
Ver comentarios