¿Qué es la búsqueda lineal?

Question

Accepted Answer

**Linear search** escanea una colección elemento por elemento hasta encontrar el objetivo o llegar al final. Funciona en **cualquier** lista — ordenada o no — pero se ejecuta en tiempo **O(n)**.

## La idea

Sin suposiciones sobre el orden: solo verifica cada elemento uno a la vez.

## Ejemplo

```python
def linear_search(arr, target):
    for i, value in enumerate(arr):   # walk left to right
        if value == target:
            return i                  # return the index when found
    return -1                         # not found after full scan

linear_search([4, 2, 7, 1], 7)        # -> 2
```

## Complejidad

- **Tiempo:** O(n) en el peor caso (objetivo al final o ausente), O(1) en el mejor caso.
- **Espacio:** O(1).

## Cuándo usarla

- Los datos están **desordenados** y no puedes permitirte ordenarlos.
- La lista es pequeña, así que O(n) es insignificante.
- Necesitas una búsqueda única donde construir un índice u ordenar primero no vale la pena.

Si buscas repetidamente, prefiere un array ordenado con binary search o un hash set para búsquedas promedio O(1).

## Por qué es importante

La búsqueda lineal es la línea base contra la cual se miden todos los demás algoritmos de búsqueda.

Te recuerda que el algoritmo *correcto* depende de los datos: desordenados y pequeños favorecen el escaneo simple; grandes y consultados repetidamente favorecen estructuras más inteligentes.

Saber cuándo O(n) es suficientemente bueno evita la optimización prematura.