Búsqueda lineal en JavaScript

B

 

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 ​​se 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.

 

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