Búsqueda binaria en JavaScript

En este artículo, veremos uno de los algoritmos de búsqueda más populares: la búsqueda binaria en JavaScript. Veremos cómo funciona, la implementación y qué lo hace tan eficiente.

Introducción

La búsqueda es una de las tareas más comúnmente realizadas en el dominio de la informática. Existen muchos algoritmos y estructuras de datos para hacer que la búsqueda sea más eficiente.

En este artículo, veremos la idea detrás de Búsqueda binaria y cómo implementarla en JavaScript.

Binary Search es un algoritmo de búsqueda muy simple, intuitivo pero eficiente. La única advertencia es que solo funciona con arreglos ordenados, por lo que podría ser necesario un preprocesamiento de nuestros datos para ordenarlos.

Comprender la búsqueda binaria

Binary Search es un algoritmo de divide y vencerás, que divide la matriz aproximadamente por la mitad cada vez que comprueba si un elemento de la matriz es el que estamos buscando.

En otras palabras, dividimos el problema en problemas más simples hasta que sea lo suficientemente simple como para resolverlos directamente. Supongamos que tenemos una matriz ordenada (en orden ascendente) y echemos un vistazo a los pasos de la búsqueda binaria:

  1. Encuentra el elemento del medio de la matriz dada.
  2. Compara el elemento del medio con el valor que estamos buscando (llamado clave).
    • If the key is less than the middle element, search in the left half.
    • If the key is more than the middle element, search in the right half.
    • If the key is equal to the middle element, return the index of the middle element.
  3. Continúe con los pasos 1, 2 hasta que nos quede un solo elemento.
  4. Si aún no se encuentra la clave, devuelva -1.

Para entender esto mejor, veamos un ejemplo de por qué podemos simplemente descartar la mitad del rango de búsqueda actual cada vez que verificamos un elemento:

binary search example

De manera similar a esta primera división, podemos seguir buceando en la matriz hasta que encontremos el elemento o terminemos con un solo candidato para la clave.

binary search example

En este caso, terminamos con un solo candidato posible para la clave, y resultó coincidir con el elemento que buscábamos.

Como puede ver en el ejemplo, nos llevó relativamente pocas comparaciones encontrar el elemento que necesitábamos. Es decir, solo necesitábamos hacer cuatro comparaciones para encontrar el elemento en una matriz de 11 elementos. Echaremos un vistazo más de cerca a la eficiencia de la búsqueda binaria más adelante, pero ya debería quedar claro que supera a los algoritmos de búsqueda simples como Búsqueda lineal.

Implementación de búsqueda binaria en JavaScript

Ahora que hemos pasado por la lógica detrás de la búsqueda binaria, implementémosla en JavaScript:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
function binarySearch(sortedArray, key){
    let start = 0;
    let end = sortedArray.length - 1;

    while (start <= end) {
        let middle = Math.floor((start + end) / 2);

        if (sortedArray[middle] === key) {
            // found the key
            return middle;
        } else if (sortedArray[middle] < key) {
            // continue searching to the right
            start = middle + 1;
        } else {
            // search searching to the left
            end = middle - 1;
        }
    }
    // key wasn't found
    return -1;
}

Aquí, estamos usando dos variables para realizar un seguimiento del ‘inicio’ y el ‘fin’ del subarreglo actual que estamos buscando. Encontramos el elemento del medio y luego verificamos si es igual, menor o mayor que la clave.

Como se explicó anteriormente, dado que tenemos una matriz ordenada, podemos descartar la mitad de los elementos de la matriz. Logramos esto en el código cambiando la variable start o end, dependiendo de dónde continuamos nuestra búsqueda. Si el elemento actual que estamos viendo es menor que la clave, cambiamos start a middle + 1 y descartamos efectivamente el elemento actual y todos los elementos menores que eso.

La eficiencia de la búsqueda binaria

La complejidad temporal de la búsqueda binaria es O(log~2~n), donde n es el número de elementos de la matriz. Esto es mucho mejor en comparación con la búsqueda lineal, que tiene una complejidad de tiempo O(n). Como muchos otros algoritmos de búsqueda, Binary Search es un algoritmo en el lugar. Eso significa que funciona directamente en la matriz original sin hacer copias.

Sin embargo, debemos tener en cuenta que la búsqueda binaria solo funciona en matrices ordenadas. El paso de clasificación en sí, si se usa un algoritmo de clasificación eficiente, tiene una complejidad de O(nlogn). Esto significa que, en la mayoría de los casos, si la matriz es pequeña o si necesitamos buscarla solo una vez, un algoritmo de fuerza bruta (por ejemplo, búsqueda lineal) podría ser mejor.

Dado esto, Binary Search realmente brilla cuando necesitamos realizar búsquedas repetidas en matrices grandes. Como se mencionó anteriormente, solo necesitábamos 4 comparaciones (las comparaciones son las tareas más intensivas de todos los algoritmos de búsqueda), para una matriz de 11 elementos. Sin embargo, si tuviéramos una matriz de 10 000 000 elementos, solo necesitaríamos verificar 24 elementos, es decir, 0.0002% de toda la matriz.

Conclusión

En este artículo, hemos echado un vistazo a la búsqueda binaria. Su lógica e implementación simples, intuitivas y eficientes lo convierten en un algoritmo muy popular para demostrar la estrategia divide y vencerás.