O que é busca linear?

Question

Accepted Answer

**Busca linear** verifica uma coleção elemento por elemento até encontrar o alvo ou atingir o fim. Funciona em **qualquer** lista — ordenada ou não — mas executa em tempo **O(n)**.

## A ideia

Nenhuma suposição sobre ordem: apenas verifique cada item um de cada vez.

## Exemplo

```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
```

## Complexidade

- **Tempo:** O(n) pior caso (alvo último ou ausente), O(1) melhor caso.
- **Espaço:** O(1).

## Quando usar

- Os dados estão **desordenados** e você não pode ordená-los.
- A lista é pequena, portanto O(n) é negligenciável.
- Você precisa de uma busca única em que construir um índice ou ordenar primeiro não vale a pena.

Se você buscar repetidamente, prefira um array ordenado com busca binária ou um conjunto hash para buscas médias O(1).

## Por que isso importa

A busca linear é a linha de base contra a qual todas as outras buscas são medidas.

Lhe lembra que o *algoritmo correto* depende dos dados: desordenado e pequeno favorece a verificação simples; grande e consultado repetidamente favorece estruturas mais inteligentes.

Saber quando O(n) é bom o suficiente evita otimização prematura.