Búsqueda lineal

La búsqueda secuencial lineal es un algoritmo para encontrar un valor dado de una función arbitraria en un cierto intervalo. Este algoritmo es el algoritmo de búsqueda más simple y, a diferencia, por ejemplo, de la búsqueda binaria , no impone ninguna restricción a la función y tiene la implementación más simple. La búsqueda del valor de una función se realiza simplemente comparando el siguiente valor en consideración (por regla general, la búsqueda se realiza de izquierda a derecha, es decir, de los valores más pequeños del argumento a los más grandes) y, si los valores coincidencia (con una u otra precisión), entonces la búsqueda se considera completada.

Si el segmento tiene longitud N, entonces es posible encontrar la solución dentro del tiempo . Que. la complejidad asintótica del algoritmo es . Debido a su baja eficiencia en comparación con otros algoritmos, la búsqueda lineal generalmente se usa solo si el segmento de búsqueda contiene muy pocos elementos, sin embargo, la búsqueda lineal no requiere memoria adicional o procesamiento / análisis de funciones, por lo que puede funcionar en modo de transmisión al obtener directamente datos de cualquier fuente. Además, la búsqueda lineal se usa a menudo en forma de algoritmos de búsqueda lineal de máximo/mínimo. $\epsilon$ ${N \over \epsilon}$ $En)$

Como ejemplo, podemos considerar la búsqueda del valor de una función en el conjunto de números enteros presentados en una tabla.

Ejemplo

Las variables y contienen, respectivamente, los límites izquierdo y derecho del segmento de matriz, donde se encuentra el elemento que necesitamos. La investigación comienza con el primer elemento del segmento. Si el valor buscado no es igual al valor de la función en el punto dado, entonces se realiza la transición al siguiente punto. Es decir, como resultado de cada verificación, el área de búsqueda se reduce en un elemento. $L$ $R$

int function LinearSearch(Array A, int L, int R, int Key); empezar para X = L a R hacer si A[X] = tecla entonces volver X devolver -1; // elemento no encontrado final;

Un ejemplo en Swift 3, con búsqueda "acelerada":

func linearSearch ( elemento : Int , en matriz : [ Int ]) -> Int ? { var matriz = matriz let realLastElement : Int ? si matriz . está vacío { devolver cero } más { RealLastElement = matriz [ matriz . contar - 1 ] matriz [ matriz . contar - 1 ] = elemento } var i = 0 ; while matriz [ i ] != elemento { yo += 1 ; } let findElement = array [ i ]; si yo == matriz . cuenta - 1 && elemento fundado != realÚltimoElemento { devolver cero } más { vuelvo yo } }

Análisis

Para una lista de n elementos, el mejor caso es aquel en el que el valor que está buscando es igual al primer elemento de la lista y solo se requiere una comparación. El peor de los casos es cuando no hay ningún valor en la lista (o está al final de la lista), en cuyo caso se necesitan n comparaciones.

Si el valor deseado está en la lista k veces y todas las ocurrencias son igualmente probables, entonces el número esperado de comparaciones

{\begin{casos}n&k=0\\[5pt]\displaystyle {\frac {n+1}{k+1}}&1\leq k\leq n.\end{casos}}

Por ejemplo, si el valor deseado aparece en la lista una vez y todas las ocurrencias son igualmente probables, entonces el número promedio de comparaciones es . Sin embargo, si se sabe que ocurre una vez, entonces n - 1 comparaciones son suficientes y el número promedio de comparaciones será igual a ${\ fracción {n+1}{2))$

\displaystyle {\frac {(n+2)(n-1)}{2n))

(para n = 2, este número es 1, que corresponde a una construcción if-then-else).

En cualquier caso, la complejidad computacional del algoritmo es O ( n ).

Aplicaciones

En general, una búsqueda lineal es muy simple de implementar y es aplicable cuando la lista contiene pocos elementos, o en el caso de una sola búsqueda en una lista desordenada.

Si se supone que se debe buscar en la misma lista una gran cantidad de veces, entonces a menudo tiene sentido preprocesar la lista, como ordenar y luego usar una búsqueda binaria , o construir alguna estructura de datos eficiente para la búsqueda. La modificación frecuente de la lista también puede influir en la elección de otras acciones, ya que requiere el proceso de reestructuración de la estructura.

Véase también

Literatura

Donald Knuth . El arte de la programación informática, volumen 3. Clasificación y búsqueda = El arte de la programación informática, vol.3. Clasificación y búsqueda. - 2ª ed. - M. : "Williams" , 2007. - S. 824. - ISBN 0-201-89685-0 .