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 encontrar una coincidencia o hasta que se haya buscado en toda la lista. [1]
Una búsqueda lineal se ejecuta en tiempo lineal en el peor de los casos y hace 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 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 todos, excepto las listas cortas. [2]
Una búsqueda lineal comprueba secuencialmente cada elemento de la lista hasta encontrar un elemento que coincida con el valor objetivo. Si el algoritmo llega al final de la lista, la búsqueda finaliza sin éxito. [1]
Dada una lista L de n elementos con valores o registros L 0 .... L n −1 , y valor objetivo T , la siguiente subrutina utiliza la búsqueda lineal para encontrar el índice del objetivo T en L . [3]
El algoritmo básico anterior realiza dos comparaciones por iteración: una para verificar si L i es igual a T y la otra 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 sea igual al objetivo, se puede eliminar la segunda comparación hasta el final de la búsqueda, lo que hace que el algoritmo sea más rápido. La búsqueda alcanzará el centinela si el objetivo no está contenido dentro de la lista. [5]
Si la lista está ordenada de tal manera que L 0 ≤ L 1 ... ≤ 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 excede el objetivo. Esta variación requiere un centinela que sea mayor que el objetivo. [6]
En el caso de 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 buscado aparece k veces en la lista, y todos los ordenamientos de la lista son igualmente probables, el número esperado de comparaciones es
Por ejemplo, si el valor buscado aparece una vez en la lista y todos los ordenamientos de la lista son igualmente probables, el número esperado de comparaciones es . Sin embargo, si se sabe que aparece una vez, entonces se necesitan como máximo n - 1 comparaciones y el número esperado de comparaciones es
(por ejemplo, para n = 2, esto es 1, lo que corresponde a una única construcción if-then-else).
De cualquier manera, asintóticamente el costo del peor caso y el costo esperado de la búsqueda lineal son ambos O ( n ).
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 es mucho 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 están organizados en orden de probabilidad decreciente, y estas probabilidades están distribuidas geométricamente , el costo de la búsqueda lineal es solo O(1). [7]
La búsqueda lineal suele ser muy sencilla de implementar y es práctica cuando la lista tiene sólo unos 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 preprocesar la lista para utilizar un método más rápido. Por ejemplo, se puede ordenar la lista y utilizar una 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 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 matrices de tamaño mediano (alrededor de 100 elementos o menos) puede resultar inviable utilizar cualquier otro. 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, porque el tiempo inicial para preparar (ordenar) los datos es comparable al de muchas búsquedas lineales. [4]
![{\displaystyle {\begin{cases}n&{\mbox{si }}k=0\\[5pt]\displaystyle {\frac {n+1}{k+1}}&{\mbox{si }}1\leq k\leq n.\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6c31d35edb255baee3eeb7111ce8a1f7d44a3878)
