Búsqueda lineal: Python, C++ Ejemplo

¿Qué es el algoritmo de búsqueda?

Un algoritmo de búsqueda está diseñado para encontrar un elemento u objeto dentro de una colección de elementos u objetos con una estructura de datos determinada. Por ejemplo, buscar la altura mínima en una lista de alturas o la marca más alta en una lista o matriz de números. Algunos algoritmos de búsqueda populares incluyen la búsqueda lineal, la búsqueda binaria, la búsqueda por saltos y la búsqueda de Fibonacci, entre otros.

¿Qué es la búsqueda lineal?

Búsqueda lineal es uno de los algoritmos de búsqueda más simples. A partir de una lista o matriz dada, busca el elemento dado uno por uno. La búsqueda lineal itera sobre toda la lista y comprueba si algún elemento en particular es igual al elemento buscado. También se le llama el búsqueda secuencial.

¿Qué hace la función de búsqueda lineal?

Una matriz de números enteros se da como "Numbers”, y una variable “elemento” contiene el número entero a buscar.

Ahora, el algoritmo de búsqueda lineal puede proporcionar el siguiente resultado:

• “-1”; esto significa que el elemento dado no se encuentra en el array.
• Cualquier número entre 0 y n-1; significa que se encuentra el elemento de búsqueda y devuelve el índice del elemento en la matriz. Aquí, "n" representa el tamaño de la matriz.

¿Cómo funciona la búsqueda lineal?

Supongamos que tenemos un arreglo que contiene números enteros. La tarea consiste en encontrar un número dado en el arreglo.

• Si el número está ubicado en la matriz, debemos devolver el índice de ese número.
• Si no se encuentra el número dado, devolverá -1.

En el diagrama de flujo, "Datos" es la matriz de números enteros, "N" es el tamaño de la matriz y el "elemento" es el número que queremos buscar en la matriz.

Diagrama de flujo para el algoritmo de búsqueda lineal:

Estos son los pasos del diagrama de flujo:

Paso 1) Lea el elemento de búsqueda, "elemento".

Paso 2) Inicializar i=0 e índice=-1.

Paso 3) Si i<N, vaya al paso 4. En caso contrario, vaya al paso 8.

Paso 4) Si Datos[i] es igual a "elemento", vaya al paso 5. De lo contrario, vaya al paso 6.

Paso 5) Índice = i (ya que el elemento se encuentra en el índice i). Vaya al paso 8.

Paso 6) yo = yo +1.

Paso 7) Vaya al paso 3.

Paso 8) Detener.

Para simplificar, proporcionamos un ejemplo con una matriz de números enteros. La búsqueda lineal también es aplicable en cadenas, matrices de objetos o estructuras.

Apodo Code para el algoritmo de búsqueda secuencial

El siguiente pseudocódigo describe la lógica de la búsqueda lineal descrita anteriormente. Recorre el array desde el primer índice y devuelve la posición si encuentra una coincidencia; de lo contrario, devuelve -1.

function linearSearch: in → Data[], item
    foundAt = -1
    for i in (0 to data.length):
        if data[i] equals item:
            // item is found in the array
            // returning the index
            return i
    // item not found in the array
    // -1 means no item found, as a negative index is not valid
    return -1

C++ Code Ejemplo de búsqueda lineal

Aquí hay un completo C++ Programa que implementa la búsqueda secuencial e imprime el índice del valor buscado.

#include <bits/stdc++.h>
using namespace std;

int linearSearch(int *arr, int item, int n) {
    int idx = -1;
    for (int i = 0; i < n; i++) {
        if (arr[i] == item) {
            idx = i;
            break;
        }
    }
    return idx;
}

int main() {
    int array[] = {1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10};
    int n = sizeof(array) / sizeof(array[0]);
    int item;
    cout << "Enter a number to search: ";
    cin >> item;
    int idx = linearSearch(array, item, n);
    if (idx >= 0) {
        cout << item << " is found at index " << idx << endl;
    } else {
        cout << "Could not find " << item << " in the array" << endl;
    }
}

Salida:

Enter a number to search: -10
-10 is found at index 14

Python Code Ejemplo de búsqueda lineal

La misma lógica en Python Utiliza un único bucle sobre los índices de la lista y devuelve la posición del elemento coincidente.

def linearSearch(data, item):
    for i in range(len(data)):
        if data[i] == item:
            return i
    return -1

data = [1, 9, 8, 7, 6, 3, 11, 4, 6, 9, 7, 2, 0, 19, -10]
item = int(input("Enter a number to search: "))
idx = linearSearch(data, item)
if idx >= 0:
    print("{} is found at index {}".format(item, idx))
else:
    print("{} was not found".format(item))

Salida:

Enter a number to search: -10
-10 is found at index 14

Análisis de complejidad del algoritmo de búsqueda lineal

En general, la complejidad temporal se refiere a la cantidad de tiempo de CPU necesario para realizar una tarea determinada. En el algoritmo de búsqueda lineal, la tarea consiste en encontrar la clave de búsqueda entre los elementos del array.

Hay tres tipos de complejidades temporales:

• Worst Case Scenario
• Mejores escenarios de casos
• Escenario de caso promedio

Complejidad temporal de la búsqueda lineal en el peor escenario posible:

Supongamos que necesitamos realizar una búsqueda lineal en un arreglo de tamaño "n". Podemos encontrar el elemento buscado entre los índices 0 y n-1. En el peor de los casos, el algoritmo intentará hacer coincidir todos los elementos del arreglo con el elemento buscado.

En ese caso, la complejidad en el peor de los casos será O(n). Aquí, “O” —notación de la gran O— se refiere a la función de complejidad.

Complejidad temporal de la búsqueda lineal en el escenario de caso Mejores:

Supongamos que buscamos un elemento que se encuentra en la primera posición del arreglo. En este caso, el algoritmo de búsqueda lineal no buscará en los n elementos del arreglo. Por lo tanto, la complejidad será O(1), lo que significa tiempo constante.

Complejidad temporal de la búsqueda lineal en el escenario de caso promedio:

Cuando se encuentra un elemento en el índice medio de la matriz, se puede decir que la complejidad promedio del caso para la búsqueda lineal es O(N), donde N significa la longitud de la matriz.

La complejidad espacial del algoritmo de búsqueda lineal:

La complejidad espacial para la búsqueda lineal es siempre O(N) porque no necesitamos almacenar ni utilizar ningún tipo de variable temporal en la función de búsqueda lineal.

Cómo mejorar el algoritmo de búsqueda lineal

La búsqueda se puede realizar varias veces a lo largo del ciclo de vida del programa. También es posible que estemos ejecutando el algoritmo de búsqueda lineal y buscando una clave específica varias veces. Podemos usar el “Algoritmo de búsqueda binaria”si la matriz es una matriz ordenada.

Supongamos que la matriz consta de 10 mil números y que el elemento de destino se encuentra en el índice 5000. Por lo tanto, el algoritmo intentará comparar 5000 elementos. Ahora bien, las comparaciones son tareas que consumen mucha CPU. Para optimizar el algoritmo de búsqueda lineal, tenemos dos opciones.

• Transposición
• Mover al frente

Transposición:

En este método, intercambiaremos el elemento de búsqueda con su elemento anterior en el array. Por ejemplo, supongamos que tenemos un array como el siguiente:

Datos[] = {1,5,9,8,7,3,4,11}

Ahora queremos buscar 4. Pasos de la Transposición:

Paso 1) El “4” se encuentra en el índice 6. Se necesitaron seis comparaciones.

Paso 2) Intercambiar datos[6] y datos[5]. Entonces la matriz de datos se verá así:

Datos[] = {1,5,9,8,7,4,3,11}

Paso 3) Busca 4 nuevamente. Encontrado en el índice 5. Esta vez se necesitaron cinco comparaciones.

Paso 4) Intercambia los datos [5] y [4]. Entonces el array de datos se verá así:

Datos[] = {1,5,9,8,4,7,3,11}

Ahora bien, si se fijan, cuanto más frecuentemente se busca una clave, más disminuye el índice. Por lo tanto, disminuye el número de comparaciones.

Pasar al frente:

En este método, intercambiamos el elemento de búsqueda al índice 0. Porque si se busca de nuevo, podemos encontrarlo en tiempo O(1).

Aplicación del algoritmo de búsqueda lineal

A continuación se muestran algunas aplicaciones de búsqueda lineal que podemos utilizar.

• Para matrices pequeñas o con solo unos pocos elementos en la lista, es más fácil utilizar la búsqueda lineal.
• El método de búsqueda lineal se puede utilizar en modo simple o matrices multidimensionales u otras estructuras de datos.
• Generalmente, la búsqueda lineal es simple y eficiente para realizar una búsqueda en datos "desordenados". Podemos recuperar fácilmente un solo dato de la lista desordenada dada.

Preguntas Frecuentes