30-50% off hundreds of digital assets! WordPress themes, video, music and more 30-50% Off Go to Sale
Advertisement
  1. Code
  2. Algorithms
Code

El algoritmo de búsqueda binaria en JavaScript

by
Difficulty:IntermediateLength:MediumLanguages:

Spanish (Español) translation by Ana Paulina Figueroa Vazquez (you can also view the original English article)

En esta publicación haré una comparación de los algoritmos de búsqueda lineal y búsqueda binaria. Verás un pseudocódigo para cada algoritmo, junto con ejemplos y una guía paso a paso para implementar cada uno.

Introducción

Siendo un programador, debes encontrar la mejor solución a un problema para que tu código no solamente sea correcto, sino eficiente. Elegir un algoritmo subóptimo puede significar un tiempo de finalización más largo, un incremento en la complejidad del código, o peor, un programa que fallará. Es posible que hayas usado un algoritmo de búsqueda para localizar elementos en una colección de datos. El lenguaje JavaScript tiene varios métodos, como find, para localizar elementos en un arreglo. Sin embargo, estos métodos usan una búsqueda lineal. Un algoritmo de búsqueda lineal comienza al principio de una lista y compara cada elemento con el valor buscado hasta encontrarlo. Esto está bien cuando tienes un pequeño número de elementos. Pero cuando estás buscando en listas grandes que tienen miles o millones de elementos, necesitas una mejor manera de localizarlos. Este es un caso en el que debes usar la búsqueda binaria. En este tutorial explicaré cómo es que funciona la búsqueda binaria y cómo implementar el algoritmo en JavaScript. Primero revisaremos el algoritmo de búsqueda lineal.

Búsqueda lineal

Comenzaremos explicando cómo implementar la búsqueda lineal en JavaScript. Vamos a crear una función llamada linearSearch que acepte un valor que sea entero o cadena y un arreglo como parámetros. La función buscará en cada elemento del arreglo para encontrar el valor y devolverá la posición del mismo en el arreglo si ha sido encontrado. Si el valor no está en el arreglo, devolverá -1. Por ejemplo, invocar linearSearch(1, [3, 4, 2, 1, 5]) devolverá el valor 3, e invocar linearSearch(0, [3, 4, 2, 1, 5]) devolverá -1.

Aquí puedes ver un pseudocódigo para nuestra función:

La implementación de JavaScript para la búsqueda lineal

Esta es una implementación de JavaScript del algoritmo de búsqueda lineal:

Es importante destacar que el algoritmo de búsqueda lineal no necesita usar una lista ordenada. Además, el algoritmo puede ser personalizado para usarse en diferentes escenarios, como buscar un arreglo de objetos por clave. Si tienes un arreglo con datos de clientes que incluya claves para el nombre y apellido, puedes revisar si el arreglo tiene un cliente con un nombre especificado. En ese caso, en vez de verificar si list[index] es igual a nuestro valor de búsqueda, revisarías list[index].first.

En el ejemplo anterior, he usado la función linearSearch en un arreglo con 5 elementos. En el peor caso, cuando el valor buscado no esté en la lista o esté al final de la misma, la función tendrá que hacer 5 comparaciones. Ya que nuestro arreglo es muy pequeño no hay necesidad de optimizar usando un algoritmo diferente. Sin embargo, a partir de un punto determinado, ya no es eficiente usar un algoritmo de búsqueda lineal, y es entonces cuando sería mejor el uso de un algoritmo de búsqueda binaria.

Búsqueda binaria

Imagina que estás jugando un juego para adivinar un número. Este te pide que adivines un número entre 1 y 100. Si tu número es demasiado alto o demasiado bajo recibirás una pista. ¿Cuál sería tu estrategia? ¿escogerías números aleatoriamente? ¿comenzarías con 1, luego 2 y así sucesivamente hasta que lo adivines correctamente? incluso si tuvieras un número de intentos ilimitado, quieres adivinar correctamente en tan pocos intentos como sea posible. Por lo tanto quizá comiences intentando con 50. Si el número es más grande puedes intentar con 75. Si es menor, entonces eso significa que el número está entre 50 y 75 y escogerías un número que esté en medio. Seguirías de esta manera hasta llegar al número correcto. Esto es similar a la manera en la que funciona la búsqueda binaria.

A diferencia de la búsqueda lineal, la búsqueda binaria usa una lista ordenada. Para buscar un valor primero comparas el valor del elemento de la mitad de la lista. Si es igual, el valor buscado ha sido encontrado. Si el valor buscado es mayor al valor del elemento de la mitad, debes buscar en la mitad superior de los datos. Luego comparas el elemento de la mitad de esta sección con el valor buscado. De manera alternativa, si el elemento es menor al elemento de la mitad, debes buscar en la mitad inferior de la lista y comparar su valor medio. La lista se divide repetidamente a la mitad hasta encontrar el elemento, o hasta que no haya más elementos en los que puedas buscar.

Para buscar el 9 en la lista:

Primero encontramos el elemento de la mitad. Este es el elemento en la posición Math.floor((first + last)/2) en donde first es el primer índice, y last es el último índice. Elegimos redondear para que, en el caso en el que el resultado sea una fracción, este se convierta en un número entero. El elemento de la mitad en esta lista es 5. Nuestro valor buscado, 9, es mayor que 5, así que buscamos en la lista:

El elemento de la mitad de este fragmento es 8. Nueve es mayor a 8, así que buscamos en la lista:

El elemento de la mitad es 9, así que podemos detener nuestra búsqueda aquí.

Aquí puedes ver algo de pseudocódigo, que expresa el algoritmo anterior para la búsqueda binaria:

Implementación de JavaScript de la búsqueda binaria

¡Ahora vamos a codificar el algoritmo de búsqueda binaria en JavaScript!

Vamos a crear una función, binarySearch, que acepta un valor y un arreglo como parámetros. Devolverá el índice en el que aparezca el valor en la lista si ha sido encontrado. Si el valor no ha sido encontrado, devuelve -1. Esta es nuestra implementación escrita en JavaScript:

Conclusión

En este tutorial vimos cómo implementar un algoritmo de búsqueda lineal y uno de búsqueda binaria. El algoritmo de búsqueda lineal es más simple y no requiere un arreglo ordenado. Sin embargo, es ineficiente usarlo con arreglos más grandes. En el peor caso, el algoritmo tendría que buscar entre todos los elementos, haciendo n comparaciones (en donde n es el número de elementos).

Por otro lado, el algoritmo de búsqueda binaria requiere que ordenes el arreglo primero y es más complicado de implementar. Sin embargo, es más eficiente incluso al considerar el costo del ordenamiento. Por ejemplo, un arreglo de 10 elementos haría como máximo 4 comparaciones en el caso de una búsqueda binaria contra 10 en una búsqueda lineal, lo que no es una gran mejora. Sin embargo, para un arreglo con 1,000,000 elementos el peor caso en la búsqueda binaria es solamente 20 comparaciones. ¡Esa es una gran mejora en comparación a la búsqueda lineal!.

Saber cómo usar la búsqueda binaria no es solamente algo que debas entrenar para las preguntas de una entrevista. Es una habilidad práctica que puede hacer que tu código trabaje mucho más eficientemente.

Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.