Búsqueda lineal en JavaScript

En este artículo, veremos uno de los algoritmos de búsqueda más simples: la búsqueda lineal en JavaScript. Implementaremos búsquedas regulares y lineales para todas las apariciones de un elemento.

Introducción

La búsqueda, en el contexto de las Ciencias de la Computación, 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 a través de una lista dada de elementos: Búsqueda lineal.

Comprensión de 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 de la lista hasta que encontremos el elemento que estamos buscando. El término técnico para el elemento que buscamos es - clave.

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 índice) del elemento. Si el elemento que estamos buscando no existe en la lista, generalmente devolvemos -1.

Implementación de búsqueda lineal en JavaScript

Podemos recorrer la lista dada usando un bucle for. Veamos la implementación de la búsqueda lineal:

1
2
3
4
5
6
7
8
function linearSearch(arr, key){
    for(let i = 0; i < arr.length; i++){
        if(arr[i] === key){
            return i
        }
    }
    return -1
}

Aquí estamos revisando todos los elementos en una matriz y comparando 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 de i.

En caso de que el elemento no exista en nuestra lista, la función linearSearch no devolverá ningún valor i del bucle. Simplemente ‘devolvemos -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 encontrar la primera aparición del elemento que estamos buscando (clave). Pero, ¿y si queremos los índices de todas las ocurrencias de un elemento dado?

Ahí es donde entra en juego 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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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 un algoritmo de fuerza bruta. Esto significa que el algoritmo no usa ninguna lógica para tratar de hacer lo que se supone que debe hacer rápidamente, o para reducir de alguna manera el rango de elementos en los que busca clave. Otros algoritmos de búsqueda tienen como objetivo hacer esto de manera más eficiente mediante algún tipo de preprocesamiento de la lista/matriz, por ejemplo, ordená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 ocurre 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, tendríamos que 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, usando 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 simple, uno que no usa ninguna lógica para tratar de descartar un rango particular para buscar o con un enfoque en la velocidad.