Búsqueda lineal

En informática, la búsqueda lineal o la búsqueda secuencial es un método para encontrar un valor objetivo dentro de una lista. Ésta comprueba secuencialmente cada elemento de la lista para el valor objetivo hasta que es encontrado o hasta que todos los elementos hayan sido comparados.

	Búsqueda Lineal
	Clase	Algoritmos de búsqueda
	Estructura de datos	{{{datos}}}
	Peor de los casos	O(n)
	Mejor de los casos	O(1)
	Caso promedio	O(n)
	Complejidad del peor de los casos	O(1) iterativo

Búsqueda lineal es en tiempo el peor, y marca como máximo n comparaciones, donde n es la longitud de la lista. Si la probabilidad de cada elemento para ser buscado es el mismo, entonces la búsqueda lineal tiene una media de n/2 comparaciones, pero esta media puede ser afectado si las probabilidades de búsqueda para cada elemento varían. La búsqueda lineal es poco práctica porque otros algoritmos de búsqueda y esquemas, como el algoritmo de búsqueda binaria y Tabla hash, es significativamente más rápido buscando todo menos listas cortas.

Algoritmo

Búsqueda lineal comprueba secuencialmente cada elemento de la lista hasta que encuentra un elemento que coincide con el valor de objetivo. Si el algoritmo llega al fin de la lista sin encontrar el objetivo, la búsqueda termina insatisfactoriamente.

Algoritmo básico

Dado una lista L de n elementos con valores o registros L0 ... Ln−1 y valor de objetivo T, la subrutina siguiente utiliza búsqueda lineal para encontrar el índice del objetivo T en L.

1. Set i a 0.
2. Si L_i = T, la búsqueda culmina exitosamente; retorna i.
3. Aumento i en 1.
4. Si i < n, regresar al paso 2. De otro modo, la búsqueda termina insatisfactoriamente.

Con un valor centinela

El algoritmo anterior, realiza dos comparaciones por iteración: uno para comprobar si Li es igual a t, y el otro para comprobar si i apunta a un índice válido de la lista. Añadiendo un valor extra Ln a la lista (un valor centinela) que es igual al objetivo, la segunda comparación puede ser eliminada hasta el fin de la búsqueda, haciendo el algoritmo más rápido. La búsqueda encontrará el centinela si el objetivo no está contenido dentro de la lista.[4]

1. Set i a 0.
2. Si  L_i = T,ir al paso 4.
3. Aumento i en 1 e ir al paso 2.
4. Si i < n , la búsqueda termina exitosamente; retorna i. Sino la búsqueda culmina insatisfactoriamente.

En una lista ordenada

Si la lista está ordenada tal que L₀ ≤ L₁ ... ≤ L_n−1 , la búsqueda puede establecer la ausencia del objetivo más deprisa al concluir la búsqueda una vez que Li supera el objetivo. Esta variación requiere un centinela cuyo valor es más grande que el objetivo.

1. Set i a 0.
2. Si  L_i ≥ T , ir al paso 4.
3. Aumento i en 1 e ir al paso 2.
4. Si L_i = T, la búsqueda termina exitosamente; retorna i. Sino la búsqueda termina sin éxito.

Análisis

Para una lista con n elementos, el mejor caso es cuándo el valor es igual al primer elemento de la lista, en este caso solo se necesita una comparación. El peor caso es cuando el valor no es en la lista (u ocurre solo una vez, al final de la lista), en este caso se necesitan n comparaciones.

Si el valor que se está buscando se presenta k veces en la lista, y todos los elementos de la lista es igualmente probables, el número esperado de comparaciones es

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

Por ejemplo, si el valor que se está buscado ocurre una vez en la lista, y todo elemento de la lista es igualmente probable, el número esperado de comparaciones es ${\frac {n+1}{2}}$ Aún así, si es sabido que ocurre una vez, entonces como máximo n - 1 comparaciones son necesitadas, y el número esperado de comparaciones es

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

(Por ejemplo, para n = 2 esto es 1, correspondiendo a un solo si-entonces-más construir).

Cualquier manera, el costo del peor caso y el costo esperado de búsqueda lineal son ambos O(n).

Probabilidades no uniformes

El rendimiento de búsqueda lineal mejora si el valor deseado es tiene mayor probabilidad de ser encontrado el principio de la lista que a su fin. Por tanto, si algunos valores son mucho más probables para ser buscados que otros, es mejor colocarlos al principio de la lista.

En particular, cuándo los elementos de lista están arreglados por orden de probabilidad decreciente, y estas probabilidades están geométricamente distribuidas, el coste de búsqueda lineal es único O(1). Si el tamaño n de lista es bastante grande, la búsqueda lineal será más rápida que búsqueda binaria, cuyo coste es O(log n).

Aplicación

La búsqueda lineal es normalmente muy sencilla de implementar, y es práctico cuándo la lista posee solo unos cuantos elementos, o cuando realiza una sola búsqueda en una lista desordenada.

Cuando muchos valores tienen que ser buscados en la misma lista, a menudo se pre-procesa la lista para utilizar un método más rápido. Por ejemplo, uno puede ordenar la lista y utilizar búsqueda binaria, o construir una estructura de datos de búsqueda eficaz de él. El contenido de la lista debería cambiar frecuentemente, repetir la reorganización puede ser más problemático de lo que vale.

Como resultado, incluso si en teoría otros algoritmos de búsqueda pueden ser más rápidos que la búsqueda lineal (por ejemplo búsqueda binaria), en la práctica, (los arreglos de tamaño medio, alrededor 100 elementos o menos) pueda ser no factible utilizar cualquier otro método. En arreglos más grandes, solo tiene sentido para utilizar otros métodos de búsqueda más rápidos si los datos son bastante grandes, porque el tiempo inicial para preparar (ordenar) los datos es comparable a muchas búsquedas lineales

Véase también

• Búsqueda ternaria
• Tabla hash

Bibliografía

• Knuth, Donald (1998). (2.º ed.). Lectura, MA: Addison-Wesley Profesional.  ISBN 0-201-89685-0 

• Datos: Q787903