Búsqueda binaria en JavaScript

B

Introducción

La búsqueda es una de las tareas más habituales en el ámbito de la informática. Existen muchos algoritmos y estructuras de datos para hacer la búsqueda más eficiente.

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

La búsqueda binaria es un algoritmo de búsqueda muy simple, intuitivo y eficiente. La única advertencia es que solo funciona con matrices ordenadas, por lo que podría ser necesario un procesamiento previo de nuestros datos para clasificarlos.

Comprensión de la búsqueda binaria

La búsqueda binaria es un algoritmo de divide y vencerás, que divide la matriz aproximadamente a la mitad cada vez que verifica si un elemento de la matriz es el que estamos buscando.

En otras palabras, dividimos el problema en problemas más simples hasta que se vuelve 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:

  • Encuentra el elemento del medio de la matriz dada.
  • Compare el elemento del medio con el valor que estamos buscando (llamado llave).
    • Si la clave es menor que el elemento del medio, busque en la mitad izquierda.
    • Si la clave es más que el elemento del medio, busque en la mitad derecha.
    • Si la clave es igual al elemento del medio, devuelve el índice del elemento del medio.
  • Continúe con los pasos 1, 2 hasta que nos quedemos con un solo elemento.
  • Si la clave aún no se encuentra, devuelve -1.
  • Para entender esto mejor, veamos un ejemplo de por qué simplemente podemos descartar la mitad del rango de búsqueda actual cada vez que verificamos un elemento:

    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.

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

    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. Más adelante veremos más de cerca la eficiencia de la búsqueda binaria, pero ya debería quedar claro que supera a los algoritmos de búsqueda simples como la búsqueda lineal.

    Implementación de búsqueda binaria en JavaScript

    Ahora que hemos analizado la lógica detrás de la búsqueda binaria, impleméntela en JavaScript:

    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 de la start y end del subarreglo actual que estamos buscando. Encontramos el elemento del medio y luego verificamos si es igual, menor o mayor que el key.

    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 el start o end variable, dependiendo de dónde continuemos nuestra búsqueda. Si el elemento actual que estamos viendo es menor que la clave, cambiamos start a middle + 1 y descartar efectivamente el elemento actual y todos los elementos menos que eso.

    La eficiencia de la búsqueda binaria

    La complejidad temporal de la búsqueda binaria es O (log2n), donde n es el número de elementos de la matriz. Esto es mucho mejor en comparación con la búsqueda lineal, que es de complejidad temporal O (n). Como muchos otros algoritmos de búsqueda, la búsqueda binaria es un algoritmo in situ. Eso significa que funciona directamente en la matriz original sin hacer ninguna copia.

    Sin embargo, debemos tener en cuenta que la búsqueda binaria solo funciona en matrices ordenadas. El paso de clasificación en sí, si utiliza 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, la búsqueda binaria 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 de divide y vencerás.

    .

    About the author

    Ramiro de la Vega

    Bienvenido a Pharos.sh

    Soy Ramiro de la Vega, Estadounidense con raíces Españolas. Empecé a programar hace casi 20 años cuando era muy jovencito.

    Espero que en mi web encuentres la inspiración y ayuda que necesitas para adentrarte en el fantástico mundo de la programación y conseguir tus objetivos por difíciles que sean.

    Add comment

    Sobre mi

    Últimos Post

    Etiquetas

    Esta web utiliza cookies propias para su correcto funcionamiento. Al hacer clic en el botón Aceptar, aceptas el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Más información
    Privacidad