Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
/**
*
* 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);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment