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 de una colección de elementos u objetos con una estructura de datos determinada. Por ejemplo, buscar la altura mínima de una lista de alturas dada, o buscar la marca más alta de una lista o matriz de números. Algunos algoritmos de búsqueda populares incluyen “Búsqueda lineal”, “Búsqueda binaria”, “Búsqueda de salto”, “Búsqueda de Fibonacci”, etc.

¿Qué es la búsqueda lineal?

La 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 verifica si algún elemento en particular es igual al elemento de búsqueda. También se denomina búsqueda lineal. 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 la matriz
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 una matriz que contiene números enteros. La tarea consiste en encontrar un número determinado en la matriz.

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) Iniciar i=0 e index=-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 artículo se encuentra en el índice no 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.

Pseudocódigo para algoritmo de búsqueda secuencial

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 negative index is not valid
return -1

C++ Ejemplo de código de búsqueda lineal

#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(arr[0]);
    int item;
    cout << "Enter a number to search: ";
    cin >> item;
    int idx = linearSearch(arr, 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 Ejemplo de código de búsqueda lineal

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 que se necesita para realizar una determinada tarea. En el algoritmo de búsqueda lineal, la tarea consiste en encontrar la clave de búsqueda en el elemento de la matriz.

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:

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

En ese caso, la complejidad en el peor de los casos será O(n). Aquí, la notación “O”-O grande significa la función de complejidad.

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

Digamos que buscamos un elemento que se encuentra en la primera posición de la matriz. En este escenario, el algoritmo de búsqueda lineal no buscará todos los n elementos de la matriz. Por lo tanto, la complejidad será O(1). Esto 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 siempre es O(N) porque no necesitamos almacenar o 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 durante el 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 comando “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 la matriz. Por ejemplo, supongamos que tiene una matriz como la 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) Intercambiar datos [5] y datos [4]. Entonces la matriz de datos se verá así:

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

Ahora, si se da cuenta, cuanto más frecuentemente se busca una clave, más disminuye el índice. Disminuyendo así el número de comparaciones.

Pasar al frente:

En este método, intercambiamos el elemento de búsqueda en el índice 0. Porque si se busca nuevamente, podemos encontrarlo en el momento 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 de tamaño pequeño o 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.

Te podría gustar: