En informática , una 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]
Clase | Algoritmo de búsqueda |
---|---|
Rendimiento en el peor de los casos | O ( n ) |
Rendimiento en el mejor de los casos | O (1) |
Rendimiento medio | O ( n / 2 ) |
Complejidad espacial en el peor de los casos | O (1) iterativo |
Una búsqueda lineal se ejecuta en el peor tiempo lineal 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 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 una búsqueda significativamente más rápida para todos menos listas cortas. [2]
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. [1]
Algoritmo basico
Dada una lista L de n elementos con valores o registros L 0 .... L n -1 , y valor objetivo T , las siguientes subrutinas usos lineal de búsqueda para encontrar el índice del objetivo T en L . [3]
- Establezca i en 0.
- Si L i = T , la búsqueda termina con éxito; volver i .
- Incrementar i en 1.
- Si i < n , vaya al paso 2. De lo contrario, la búsqueda finaliza sin éxito.
Con un centinela
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 iguale al objetivo, la segunda comparación se puede eliminar hasta el final de la búsqueda, haciendo que el algoritmo sea más rápido. La búsqueda llegará al centinela si el objetivo no está incluido en la lista. [4]
- Establezca i en 0.
- Si L i = T , vaya al paso 4.
- Aumente i en 1 y vaya al paso 2.
- Si i < n , la búsqueda termina con éxito; volver i . De lo contrario, la búsqueda termina sin éxito.
En una mesa ordenada
Si la lista está ordenada de modo 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 supera el objetivo. Esta variación requiere un centinela que sea mayor que el objetivo. [5]
- Establezca i en 0.
- Si L i ≥ T , vaya al paso 4.
- Aumente i en 1 y vaya al paso 2.
- Si L i = T , la búsqueda termina con éxito; volver i . De lo contrario, 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 de los casos 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 ocurre 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 ocurre 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 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 de su 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 se organizan en orden de probabilidad decreciente, y estas probabilidades están distribuidas geométricamente , el costo de la búsqueda lineal es solo O (1). [6]
Solicitud
La búsqueda lineal suele ser muy sencilla de implementar y resulta práctica cuando la lista tiene solo 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, 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 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 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 no ser factible utilizar 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. [7]
Ver también
Referencias
Citas
- ^ a b 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". Clasificación y búsqueda . El arte de la programación informática. 3 (3ª ed.). Addison-Wesley. págs. 396–408. ISBN 0-201-89685-0.
- ^ Horvath, Adam. "Búsqueda binaria y rendimiento de búsqueda lineal en la plataforma .NET y Mono" . Consultado el 19 de abril de 2013 .
Obras
- Knuth, Donald (1998). Clasificación y búsqueda . El arte de la programación informática . 3 (2ª ed.). Reading, MA: Addison-Wesley Professional.ISBN 0-201-89685-0