En informática , la 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. [1]
Una búsqueda lineal se ejecuta en el peor de los casos en tiempo lineal 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 caso promedio den+1/2comparaciones, 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 búsquedas significativamente más rápidas para todo menos 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 hace 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, 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á incluido en la lista. [5]
Si la lista está ordenada de 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 Li excede el objetivo. Esta variación requiere un centinela que sea mayor que el objetivo. [6]
Para una lista con n elementos, el mejor caso es cuando el valor es igual al primer elemento de la lista, en cuyo caso sólo 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 todos los ordenamientos de la lista son igualmente probables, el número esperado de comparaciones es
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 . 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
(por ejemplo, para n = 2 esto es 1, correspondiente a una única construcción si-entonces-si no).
De cualquier manera, asintóticamente el costo del peor de los casos y el costo esperado de la búsqueda lineal son O ( n ).
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 del 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 resulta práctica cuando la lista tiene sólo unos pocos elementos o cuando se realiza una única búsqueda en una lista desordenada.
Cuando es necesario buscar muchos valores en la misma lista, a menudo vale la pena preprocesar la lista para utilizar un método más rápido. Por ejemplo, se puede ordenar la lista y utilizar la búsqueda binaria , o 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 de lo que vale la pena.
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), podría resultar inviable utilizar cualquier otra cosa. En matrices más grandes, sólo 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 a muchas búsquedas lineales. [4]
![{\displaystyle {\begin{casos}n&{\mbox{if }}k=0\\[5pt]\displaystyle {\frac {n+1}{k+1}}&{\mbox{if }}1 \leq k\leq n.\end{casos}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6c31d35edb255baee3eeb7111ce8a1f7d44a3878)
