Algoritmo de búsqueda binaria en JavaScript

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 > mayor qué y < 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

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.

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:

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:

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

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.

2 pensamientos sobre “Algoritmo de búsqueda binaria en JavaScript”

  1. Pingback: Algoritmo de búsqueda binaria en muchos lenguajes de programación - Parzibyte's blog

  2. Pingback: Algoritmo de búsqueda binaria en listas y arreglos de Python - Parzibyte's blog

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *