Búsqueda lineal

En informática, una búsqueda lineal o búsqueda 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.

Una búsqueda lineal se ejecuta en el peor tiempo lineal y hace como mucho 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 caso promedio de n+1/2 comparaciones, pero el caso 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 una búsqueda significativamente más rápida para todas las listas excepto para las cortas.

Algoritmo

Una búsqueda lineal verifica secuencialmente cada elemento de la lista hasta que encuentra un elemento que coincide con el valor objetivo. Si el algoritmo llega al final de la lista, la búsqueda termina sin éxito.

Algoritmo básico

Dada una lista L de n elementos con valores o registra L₀.... L_{n− 1} y el valor de destino T, la siguiente subrutina utiliza la búsqueda lineal para encontrar el índice de la T en L.

1. Set i a 0.
2. Si L_i = T, la búsqueda termina con éxito; retorno i.
3. Aumento i por 1.
4. Si i. n, ir al paso 2. De lo contrario, la búsqueda termina sin éxito.

Con un centinela

El algoritmo básico anterior hace dos comparaciones por iteración: una para comprobar si L_i es igual a T, y el otro para verificar si i todavía apunta a un índice válido de la lista. Al agregar un registro adicional L_n a la lista (un valor centinela) que equivale a el objetivo, la segunda comparación se puede eliminar hasta el final de la búsqueda, lo que hace que el algoritmo sea más rápido. La búsqueda llegará al centinela si el objetivo no está contenido en la lista.

1. Set i a 0.
2. Si L_i = T, ir al paso 4.
3. Aumento i por 1 e ir al paso 2.
4. Si i. n, la búsqueda termina con éxito; retorno i. Else, la búsqueda termina sin éxito.

En una tabla ordenada

Si la lista está ordenada de tal manera que L₀ ≤ L₁... ≤ 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 el objetivo. Esta variación requiere un centinela que sea mayor que el objetivo.

1. Set i a 0.
2. Si L_i ≥ T, ir al paso 4.
3. Aumento i por 1 e ir al paso 2.
4. Si L_i = T, la búsqueda termina con éxito; retorno i. Else, la búsqueda termina sin éxito.

Análisis

Para una lista con n elementos, el mejor caso es cuando el valor es igual al primer elemento de la lista, en cuyo caso solo se necesita una comparación. El peor caso es 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 que se busca aparece k veces en la lista, y todas las ordenaciones de la lista son igualmente probables, el número esperado de comparaciones es

{}nsik=0n+1k+1si1≤ ≤ k≤ ≤ n.{displaystyle {begin{cases}n ## k=0[5pt]displaystyle {frac {n+1}{mbox{if} {c}{c} {c}} {cc}}} {cc}}}}} {mbox {mbox{if} {c}}}}} {ccc}}}}}}} {mbox {mbox {mbox {c} {c}}}{c}}{c}}}}}}}}{c}}}}}}}}}{c}}}}} {c}}}}}}}}}}}}}}}}}}}}}{c}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} #1leq kleq n.end{cases}}

Por ejemplo, si el valor que se busca ocurre una vez en la lista, y todos los pedidos de la lista son igualmente probables, el número esperado de comparaciones es n+12{fnMicroc} {n+1}{2}}. Sin embargo, si es conocido que ocurre una vez, entonces a la mayoría n - Se necesitan 1 comparaciones y el número previsto de comparaciones

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

(por ejemplo, para n = 2, esto es 1, correspondiente a una sola construcción if-then-else).

De cualquier manera, asintóticamente el costo del 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 esté cerca del principio de la lista que al final. Por lo tanto, si es más probable que se busquen algunos valores que otros, es conveniente colocarlos al principio de la lista.

En particular, cuando los elementos de la lista se organizan en orden de probabilidad decreciente y estas probabilidades se distribuyen geométricamente, el costo de la búsqueda lineal es solo O(1).

Solicitud

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

Cuando se deben buscar muchos valores en la misma lista, a menudo vale la pena procesar previamente la lista para usar un método más rápido. Por ejemplo, uno puede ordenar la lista y usar la búsqueda binaria, o construir 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 ser más problemática de lo que vale.

Como resultado, 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 arreglos de tamaño mediano (alrededor de 100 elementos o menos), podría ser inviable usar cualquier otra cosa.. En arreglos más grandes, solo tiene sentido usar otros métodos de búsqueda más rápidos si los datos son lo suficientemente grandes, porque el tiempo inicial para preparar (ordenar) los datos es comparable a muchas búsquedas lineales.