Algoritmo de búsqueda binaria en JavaScript

Publicado por parzibyte en

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.


parzibyte

He trabajado por más de 4 años en el desarrollo de software con experiencia en Java, PHP, JavaScript, HTML, Node.JS, Python, Android y Go. También he trabajado con bases de datos SQL como MySQL y SQLite, así como con bases de datos NoSQL usando MongoDB.Soy bueno utilizando algunos frameworks y herramientas como Firebase, jQuery, AngularJS, VueJS, CodeIgniter, Laravel, BulmaCSS, Bootstrap y Electron.Otros términos que conozco son: Arduino, GraphQL, API's, REST, AJAX, PouchDB, CouchDB, Experiencia de usuario, buenas prácticas de programación, Webpack, NPM, Administración de servidores y programación de scriptsLa plataforma en la que tengo más experiencia es la web, pero en mis ratos libres realizo unos pequeños ejercicios en C# y C.Estoy aquí para ayudarte a resolver tus problemas de programación y depuración :-)

2 Comments

Algoritmo de búsqueda binaria en listas y arreglos de Python - Parzibyte's blog · octubre 30, 2018 a las 10:52 pm

[…] Búsqueda binaria en JavaScript […]

Algoritmo de búsqueda binaria en muchos lenguajes de programación - Parzibyte's blog · noviembre 8, 2018 a las 11:33 am

[…] JavaScript: búsqueda binaria en arreglo usando recursión y while […]

Deja un comentario

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.

A %d blogueros les gusta esto: