Búsqueda lineal

Definición

Algoritmo que examina secuencialmente los elementos de una colección hasta encontrar el valor buscado o agotar la colección.

Formulación

para c = 1 hasta n:
    si A[c] = x: devolver c
devolver NULL

Ejemplo mínimo

Para $A=[4,7,2]$ y $x=7$, compara primero con $4$ y después con $7$; devuelve la posición 2.

Análisis

• Terminación: a lo más $n$ iteraciones.
• Validez: revisa todas las posiciones hasta encontrar $x$.
• Tiempo en peor caso: $O(n)$.
• Espacio auxiliar: $O(1)$.

Contraejemplo o límites

No aprovecha que la colección esté ordenada. Otras estructuras o algoritmos pueden permitir búsquedas más rápidas bajo supuestos adicionales.

Relaciones

• Es un caso de: Algoritmo.
• Ilustra: terminación, validez, tiempo y espacio.

Procedencia

• Clase: Introducción al curso
• Fuente: presentación introductoria, diapositivas 12–13.