Búsqueda lineal

En informática , la búsqueda lineal o secuencial es un método para encontrar un elemento dentro de una lista . Comprueba secuencialmente cada elemento de la lista hasta que se encuentra una coincidencia o se ha buscado en toda la lista. ^{[ 1 ]}

Una búsqueda lineal se ejecuta en tiempo lineal en el peor de los casos y realiza como máximo $n$ comparaciones, donde $n$ es la longitud de la lista. Si cada elemento tiene la misma probabilidad de ser buscado, entonces la búsqueda lineal tiene un promedio de $n +1 / 2$ comparaciones, pero este promedio puede verse afectado si las probabilidades de búsqueda para cada elemento varían. La búsqueda lineal rara vez es práctica porque otros algoritmos y esquemas de búsqueda, como el algoritmo $de$ búsqueda binaria y las tablas hash , permiten búsquedas significativamente más rápidas para todas las listas, excepto las cortas. ^{[ 2 ]}

Algoritmo

Una búsqueda lineal comprueba secuencialmente cada elemento de la lista hasta encontrar uno que coincida con el valor objetivo. Si el algoritmo llega al final de la lista, la búsqueda finaliza sin éxito. ^{[ 1 ]}

Algoritmo básico

Dada una lista $L$ de $n$ elementos con valores o registros $L 0 .... L n -1$ , y un valor objetivo $T$ , la siguiente subrutina utiliza una búsqueda lineal para encontrar el índice del objetivo $T$ en $L$ . ^{[ 3 ]}

Establezca $i$ en 0.
Si $L i = T$ , la búsqueda finaliza con éxito; devuelve $i$ .
Incrementa $i$ en 1.
Si $i < n$ , vaya al paso 2. De lo contrario, la búsqueda finaliza sin éxito.

Podemos definir esto en pseudocódigo como se muestra a continuación, utilizando un enfoque iterativo o recursivo.

La función iterativeLinearSearch( lista L, T) es para i = 0 hasta length(L) hacer si L[i] == T entonces devolver i // Devuelve un valor de error (en este caso, -1). devolver -1 función recursiveLinearSearch( lista L, T, i = 0) es si L[i] == [T] entonces devolver i si i > longitud(L) entonces devolver -1 // Valor fallido. return recursiveLinearSearch(L, T, i = i + 1)

Con un centinela

El algoritmo básico anterior realiza dos comparaciones por iteración: una para comprobar si $L i$ es igual a T , y otra para comprobar si $i$ todavía apunta a un índice válido de la lista. Al añadir un registro adicional $L n$ a la lista (un valor centinela ) que sea igual al objetivo, se puede eliminar la segunda comparación hasta el final de la búsqueda, lo que acelera el algoritmo. La búsqueda alcanzará el valor centinela si el objetivo no está contenido en la lista. ^{[ 4 ]}

Establezca $i$ en 0.
Si $L i = T$ , vaya al paso 4.
Incrementa $i$ en 1 y ve al paso 2.
Si $i < n$ , la búsqueda finaliza correctamente; devuelve $i$ . En caso contrario, la búsqueda finaliza sin éxito.

Podemos definir esto en pseudocódigo como se muestra a continuación, utilizando un enfoque iterativo o recursivo.

La función iterativeSentinelSearch( lista L, T) es para i = 0 hasta length(L) hacer si L[i] == T entonces si i < length(L) entonces devolver i sino devolver -1 devolver -1 La función recursiveSentinelSearch( lista L, T, i = 0) es si i >= length(L) entonces devuelve -1 si L[i] == T entonces devuelve i devuelve recursiveSentinelSearch(L, T, i = i + 1)

En una tabla ordenada

Si la lista se ordena de tal manera que $L 0 \leq L 1 ... \leq L n -1$ , la búsqueda puede establecer la ausencia del objetivo más rápidamente al concluir la búsqueda una vez que $L i$ supera al objetivo. Esta variación requiere un centinela que sea mayor que el objetivo. ^{[ 5 ]}

Establezca $i$ en 0.
Si $L i \geq T$ , vaya al paso 4.
Incrementa $i$ en 1 y ve al paso 2.
Si $L i = T$ , la búsqueda finaliza correctamente; devuelve $i$ . En caso contrario, la búsqueda finaliza sin éxito.

Podemos definir esto en pseudocódigo como se muestra a continuación, utilizando un enfoque iterativo o recursivo.

La función iterativeTableSearch( lista L, T) es para i = 0 hasta length(L) hacer si L[i] >= T entonces si L[i] == T entonces devolver i sino devolver -1 devolver -1 La función recursiveTableSearch( lista L, T, i = 0) es: si i >= length(L) entonces devuelve -1 si L[i] >= T entonces si L[i] == T entonces devuelve i sino devuelve -1 devuelve recursiveTableSearch(L, T, i = i + 1)

Análisis

Para una lista con n elementos, el mejor caso se da cuando el valor es igual al primer elemento de la lista, en cuyo caso solo se necesita una comparación. El peor caso se da cuando el valor no está en la lista (o aparece solo una vez al final de la lista), en cuyo caso se necesitan n comparaciones.

Si el valor buscado aparece k veces en la lista, y todos los ordenamientos de la lista son igualmente probables, el número esperado de comparaciones es

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

Por ejemplo, si el valor que se busca aparece una vez en la lista y todos los ordenamientos de la lista son igualmente probables, el número esperado de comparaciones es ${\frac {n+1}{2}}$ Sin embargo, si se sabe que ocurre una vez, entonces se necesitan como máximo n − 1 comparaciones, y el número esperado de comparaciones es

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

(por ejemplo, para n = 2 esto es 1, lo que corresponde a una única estructura if-then-else).

De cualquier manera, asintóticamente el costo en el peor de los casos y el costo esperado de la búsqueda lineal son ambos O ( n ).

Probabilidades no uniformes

El rendimiento de la búsqueda lineal mejora si es más probable que el valor deseado se encuentre cerca del principio de la lista que al final. Por lo tanto, si algunos valores tienen mucha más probabilidad de ser buscados que otros, es conveniente colocarlos al principio de la lista.

En particular, cuando los elementos de la lista están ordenados según su probabilidad decreciente, y estas probabilidades se distribuyen geométricamente , el costo de la búsqueda lineal es solo O(1). ^{[ 6 ]}

En general, si los elementos están ordenados en orden de probabilidad decreciente y la probabilidad de buscar el i- ésimo elemento es $p_{i}$ , el costo esperado de una sola búsqueda es $ES^{OPT}=\sum _{i=1}^{n}ip_{i}$ Bajo el supuesto natural de que las probabilidades no se conocen de antemano, o no se puede dedicar tiempo a ordenar la lista por probabilidades, se puede utilizar el enfoque de una estructura de datos autoajustable y mover los elementos hacia el principio de la lista cuando se solicitan en una búsqueda. Dos heurísticas naturales para este autoajuste son Mover al Frente (MF) y Transponer (T), donde el elemento solicitado intercambia lugares con su predecesor. Se sabe que el costo esperado de un acceso en una secuencia larga de accesos independientes, promediado sobre todos los órdenes iniciales de la lista, satisface $ES^{T}\leq ES^{MF}\leq {\frac {\pi }{2}}ES^{OPT}$ En términos de costo amortizado , promediando sobre una secuencia de operaciones en el peor de los casos (nota: entre secuencias que satisfacen el supuesto sobre probabilidades), tenemos $S^{MF}\leq 2S^{OPT}$ , mientras $S^{T}$ puede ser tan malo como $O(mS^{OPT})$ . ^{[ 7 ]}

Solicitud

La búsqueda lineal suele ser muy sencilla de implementar y resulta práctica cuando la lista tiene pocos elementos o cuando se realiza una única búsqueda en una lista desordenada.

Cuando se deben buscar muchos valores en la misma lista, suele ser conveniente preprocesarla para usar un método más rápido. Por ejemplo, se puede ordenar la lista y usar la búsqueda binaria , o bien crear una estructura de datos de búsqueda eficiente a partir de ella. Si el contenido de la lista cambia con frecuencia, la reorganización repetida puede resultar más problemática que beneficiosa.

En consecuencia, aunque en teoría otros algoritmos de búsqueda pueden ser más rápidos que la búsqueda lineal (por ejemplo, la búsqueda binaria ), en la práctica, incluso en matrices de tamaño medio (alrededor de 100 elementos o menos), podría ser inviable utilizar cualquier otro método. En matrices más grandes, solo tiene sentido utilizar otros métodos de búsqueda más rápidos si los datos son lo suficientemente grandes, ya que el tiempo inicial para preparar (ordenar) los datos es comparable al de muchas búsquedas lineales. ^{[ 8 ]}

Véase también

Referencias

Citas

1 2 Knuth 1998 , §6.1 ("Búsqueda secuencial").
↑ Knuth 1998 , §6.2 ("Búsqueda por comparación de claves").
↑ Knuth 1998 , §6.1 ("Búsqueda secuencial"), subsección "Algoritmo B".
↑ Knuth 1998 , §6.1 ("Búsqueda secuencial"), subsección "Algoritmo Q".
↑ Knuth 1998 , §6.1 ("Búsqueda secuencial"), subsección "Algoritmo T".
↑ Knuth, Donald (1997). «Sección 6.1: Búsqueda secuencial». Ordenación y búsqueda . El arte de la programación informática. Vol. 3 (3.ª ed.). Addison-Wesley. págs. 396–408 . ISBN 0-201-89685-0.
↑ Baeza-Yates, Ricardo; Poblete, Patricio V. (1999). «Capítulo 2: Búsqueda». En Atallah (ed.). Algoritmos y teoría de la computación: Manual . CRC Press. pp. 2–3 . ISBN 0849326494.
↑ Horvath, Adam. "Rendimiento de la búsqueda binaria y lineal en la plataforma .NET y Mono" . Consultado el 19 de abril de 2013 .

Obras

Knuth, Donald (1998). Ordenación y búsqueda . El arte de la programación informática . Vol. 3 (2.ª ed.). Reading, MA: Addison-Wesley Professional.ISBN 0-201-89685-0

[FOOTNOTEKnuth1998§6.1_("Sequential_search")-1] 1 2 Knuth 1998 , §6.1 ("Búsqueda secuencial").

[FOOTNOTEKnuth1998§6.2_("Searching_by_Comparison_Of_Keys")-2] Knuth 1998 , §6.2 ("Búsqueda por comparación de claves").

[FOOTNOTEKnuth1998§6.1_("Sequential_search"),_subsection_"Algorithm_B"-3] Knuth 1998 , §6.1 ("Búsqueda secuencial"), subsección "Algoritmo B".

[FOOTNOTEKnuth1998§6.1_("Sequential_search"),_subsection_"Algorithm_Q"-4] Knuth 1998 , §6.1 ("Búsqueda secuencial"), subsección "Algoritmo Q".

[FOOTNOTEKnuth1998§6.1_("Sequential_search"),_subsection_"Algorithm_T"-5] Knuth 1998 , §6.1 ("Búsqueda secuencial"), subsección "Algoritmo T".

[knuth-6] Knuth, Donald (1997). «Sección 6.1: Búsqueda secuencial». Ordenación y búsqueda . El arte de la programación informática. Vol. 3 (3.ª ed.). Addison-Wesley. págs. 396–408 . ISBN 0-201-89685-0.

[7] Baeza-Yates, Ricardo; Poblete, Patricio V. (1999). «Capítulo 2: Búsqueda». En Atallah (ed.). Algoritmos y teoría de la computación: Manual . CRC Press. pp. 2–3 . ISBN 0849326494.

[:0-8] Horvath, Adam. "Rendimiento de la búsqueda binaria y lineal en la plataforma .NET y Mono" . Consultado el 19 de abril de 2013 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]