Busca Linear¶

A busca linear inspeciona os elementos da esquerda para a direita até encontrar o alvo ou esgotar a sequência. Ela não exige ordenação.

Contrato¶

Entrada: um array de inteiros e um alvo.
Saída: o menor índice que contém o alvo, ou -1 quando estiver ausente.
O array não é modificado.

static int linearSearch(int[] values, int target) {
    for (int i = 0; i < values.length; i++) {
        if (values[i] == target) return i;
    }
    return -1;
}

Correção¶

No início da iteração i, nenhum índice em [0, i) contém o alvo. Se values[i] corresponder, i será, portanto, o primeiro índice correspondente. Caso contrário, o invariante se estende a [0, i + 1). Se o laço terminar, todo índice válido foi descartado; logo, retornar -1 está correto.

Complexidade¶

melhor caso: Θ(1) quando o primeiro elemento corresponde;
pior caso: Θ(n) quando o alvo está ausente ou é o último elemento;
espaço auxiliar: Θ(1).

Exercícios¶

Retorne todos os índices correspondentes, não apenas o primeiro.
Generalize o método usando List<T> e Objects.equals.
Explique quando a busca linear é preferível à ordenação seguida de busca binária.