B煤squeda lineal en JavaScript

     

    Introducci贸n

    La b煤squeda, en el contexto de la inform谩tica, es el proceso de localizar un elemento en particular en la lista / matriz dada. Si prestamos mucha atenci贸n, podemos encontrar algoritmos de b煤squeda en todas partes.

    Considere el proceso de iniciar sesi贸n en un sitio web. El correo electr贸nico y la contrase帽a ingresados 鈥嬧媠e buscan en los pares clave-valor existentes en la base de datos para validar al usuario.

    En este art铆culo, veamos el algoritmo m谩s b谩sico para buscar en una lista determinada de elementos: la b煤squeda lineal.

    Comprensi贸n de la b煤squeda lineal

    El algoritmo de b煤squeda lineal es un conjunto de instrucciones para recorrer la lista dada y verificar cada elemento en la lista hasta que encontremos el elemento que estamos buscando. El t茅rmino t茅cnico para el elemento que buscamos es: llave.

    El algoritmo va desde el elemento m谩s a la izquierda (o inicial) y contin煤a buscando hasta que encuentra el elemento deseado o recorre todos los elementos de la lista.

    Si se encuentra el elemento, devolveremos la posici贸n (o index) del elemento. Si el elemento que buscamos no existe en la lista, generalmente devolvemos -1.

    Implementaci贸n de b煤squeda lineal en JavaScript

    Podemos recorrer la lista dada usando un for lazo. Veamos la implementaci贸n de la b煤squeda lineal:

    function linearSearch(arr, key){
        for(let i = 0; i < arr.length; i++){
            if(arr[i] === key){
                return i
            }
        }
        return -1
    }
    

    Aqu铆 revisamos todos los elementos de una matriz y comparamos cada elemento con la clave. Si encontramos una coincidencia, devolvemos el 铆ndice del elemento. En nuestro caso, la variable i realiza un seguimiento de d贸nde estamos en la matriz, y si encontramos una coincidencia, devolvemos el valor actual para i.

    En caso de que el elemento no exista en nuestra lista, el linearSearch la funci贸n no devolver谩 ninguno i valor del bucle. Nosotros solo return -1 despu茅s del ciclo para mostrar que la funci贸n no encontr贸 el elemento deseado.

    B煤squeda lineal global

    En la implementaci贸n anterior, devolvemos un valor despu茅s de encontrarnos con la primera aparici贸n del elemento que estamos buscando (key). Pero, 驴y si queremos los 铆ndices de todas las apariciones de un elemento dado?

    Ah铆 es donde entra la b煤squeda lineal global. Es una variante de la b煤squeda lineal en la que buscamos m煤ltiples ocurrencias de un elemento dado.

    Veamos la implementaci贸n de la b煤squeda lineal global:

    function globalLinearSearch(arr, key){
        let results = []
        for(let i = 0; i < arr.length; i++){
            if(arr[i] === key){
                results.push(i)
            }
        }
        // If results array is empty, return -1
        if(!results){
            return -1
        }
    
        return results
    }
    

    En este caso, en lugar de devolver inmediatamente el 铆ndice del elemento coincidente, lo almacenamos en una matriz. Al final, estamos devolviendo la matriz de 铆ndices.

    La eficiencia de la b煤squeda lineal

    La b煤squeda lineal es un ejemplo cl谩sico de algoritmo de fuerza bruta. Esto significa que el algoritmo no usa ninguna l贸gica para intentar hacer lo que se supone que debe hacer r谩pidamente, o para reducir de alguna manera el rango de elementos en los que busca key. Otros algoritmos de b煤squeda tienen como objetivo hacer esto de manera m谩s eficiente mediante alg煤n tipo de procesamiento previo de la lista / matriz, por ejemplo, clasific谩ndola.

    La complejidad temporal de la b煤squeda lineal es O (n), donde n es el n煤mero de elementos de la lista que estamos buscando. Esto se debe a que siempre consideramos el peor de los casos al calcular la complejidad del tiempo. En el caso de la b煤squeda lineal (como con la mayor铆a de los algoritmos de b煤squeda), el peor de los casos ocurre cuando el elemento no existe en la lista. En esta situaci贸n, necesitar铆amos revisar todos los n elementos para determinar que el elemento no est谩 all铆.

    Conclusi贸n

    En este art铆culo, hemos visto la l贸gica detr谩s de la b煤squeda lineal y luego, utilizando ese conocimiento, implementamos el algoritmo en JavaScript. Tambi茅n hemos analizado la complejidad del tiempo para el algoritmo de b煤squeda lineal.

    Es, con mucho, el algoritmo de b煤squeda m谩s simple, uno que no usa ninguna l贸gica para intentar descartar un rango particular para buscar o con un enfoque en la velocidad.

     

    Etiquetas:

    Deja una respuesta

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