Búsqueda lineal para niños

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 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 Plantilla:= 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 esta contenido dentro de la lista.[4]

1. Set i a 0.
2. Si  L_i Plantilla:= 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 Plantilla:= T, la búsqueda termina exitosamente; retorna i. Sino la búsqueda termina sin éxito.

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 un 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 el 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 muchos búsquedas lineales

Véase también

En inglés: Linear search Facts for Kids

• Búsqueda ternaria
• Tabla hash