Algoritmo De Búsqueda Binaria En Javascript

Es muy probable que mientras estudias ciencias de la computación te encuentres con el ejercicio típico de realizar un algoritmo de búsqueda binaria. En este post tipo 101 explico como hacerlo con javascript de forma correcta y eficiente.

¿Cómo funciona?

El algoritmo de búsqueda binaria compara el valor que estamos buscando con el valor central de un arreglo ordenado. Si el valor es igual al punto medio decimos que lo encontramos, de lo contrario repetimos buscando en las mitad inferior y superior, según sea el caso, hasta que lo encontramos.

Tomemos como base el siguiente arreglo:

Hay que notar que un requisito para hacer la búsqueda binaria es que el arreglo este ordenado de mayor a menor, de lo contrario las optimizaciones no funcionarían y eventualmente la búsqueda daría un falso negativo.

Entonces del diagrama anterior, supongamos que estamos buscando el numero 100, los pasos serían:

1. Encontrar el punto medio
2. ¿El punto medio es 100? (no, es 400)
3. ¿100 es mayor que 400? (no, entonces buscamos en la mitad inferior)
4. Encontrar el punto medio de la mitad inferior
5. ¿El segundo punto medio es 100? (no, es 200)
6. ¿Es 100 mayor que 200? (no, entonces buscar en la mitad inferior)
7. Encontrar el punto medio de la tercera mitad inferior.
8. Como ya solo queda uno lo comparamos y si es igual a 100 lo encontramos y si no, no esta en la lista

Entonces una función corta para implementar esta búsqueda sería así:

function busquedaBinaria(arr, busqueda) {

  const puntoMedio = Math.floor(arr.length / 2);

  if (arr[puntoMedio] === busqueda) {
    return arr[puntoMedio];
  }

  if (arr[puntoMedio] < busqueda && arr.length > 1) {
   return busquedaBinaria(arr.slice(puntoMedio), busqueda);
  }

  if (arr[puntoMedio] > busqueda && arr.length > 1) {
   return busquedaBinaria(arr.slice(0, puntoMedio), busqueda);
  }

  return "no encontrado :(";
}

Véalo en acción en este fiddle:

La búsqueda binaria es uno de los algoritmos fundamentales en cuanto ciencias de la computación se refiere.

Una aplicación interesante es la de encontrar la raíz cuadrada de un numero (aproximadamente) utilizando búsquedas binarias en funciones continuas. Supongamos que queremos encontrar ?67. Bien sabemos con exactitud que 8² = 64 y que 9² = 81, por lo tanto la solución debe estar en algún punto entre 8 y 9, si aplicamos una búsqueda binaria podríamos encontrar la solución muy rápido con un margen de error aceptable. Esto funciona bien cuando tenemos funciones monótnas lo cual es bastante genial 🙂