Busca sequencial e binária: passos contados e notação Big O

Buscar um valor em uma lista é o problema mais simples de algoritmos e o melhor para entender complexidade. Duas estratégias aparecem em provas de TI: a busca sequencial e a busca binária. Os passos abaixo foram contados executando o código em um teste, para que você compare números reais e não apenas a teoria.

O vetor de exemplo

Considere um vetor ordenado de 13 elementos, com posições numeradas a partir de 0:

Posição	0	1	2	3	4	5	6	7	8	9	10	11	12
Valor	3	8	12	17	21	25	31	40	46	52	60	71	85

Busca sequencial (linear)

A busca sequencial examina os elementos um a um, do início ao fim, até achar o valor ou esgotar a lista. Não exige que o vetor esteja ordenado.

def sequencial(v, x):
    for i, e in enumerate(v):
        if e == x:
            return i
    return -1

Contagem de comparações no teste:

Procurado	Posição achada	Comparações
3 (primeiro)	0	1
46	8	9
85 (último)	12	13
50 (inexistente)	nenhuma	13

No melhor caso, uma comparação; no pior, todas as n. Por isso diz-se que a busca sequencial é O(n): o esforço cresce proporcionalmente ao tamanho da lista.

Busca binária

A busca binária exige o vetor ordenado. A cada passo compara-se o valor procurado com o elemento do meio e descarta-se metade do intervalo: se o procurado é maior, segue-se para a direita; se menor, para a esquerda.

def binaria(v, x):
    lo, hi = 0, len(v) - 1
    while lo <= hi:
        meio = (lo + hi) // 2
        if v[meio] == x:
            return meio
        if v[meio] < x:
            lo = meio + 1
        else:
            hi = meio - 1
    return -1

Procurando o 46, o teste registrou quatro passos:

Passo	lo	hi	meio	v[meio]	Decisão
1	0	12	6	31	46 é maior: vai à direita
2	7	12	9	52	46 é menor: vai à esquerda
3	7	8	7	40	46 é maior: vai à direita
4	8	8	8	46	achou na posição 8

Quatro comparações contra nove da sequencial. Para o 85 (último), também foram quatro; para o 3, três. Para o 50, que não existe, o teste fez quatro tentativas e concluiu que não está no vetor, em vez das 13 da sequencial.

Por que é O(log n)

Cada passo divide o intervalo ao meio. O número máximo de passos é o menor inteiro que satisfaz 2 elevado a esse número não ser menor que n + 1, o que equivale a “parte inteira de log2(n) mais 1”. Valores conferidos:

Tamanho n	Máximo de passos na binária
10	4
100	7
1.000	10
1.000.000	20

Um milhão de elementos exige no máximo 20 comparações; a sequencial poderia exigir um milhão. A vantagem cresce com a lista, mas há um custo: o vetor precisa estar ordenado, e ordenar também tem preço (veja algoritmos de ordenação passo a passo). Para poucas buscas numa lista que muda toda hora, a sequencial pode compensar.

Notação Big O

A notação Big O descreve como o custo cresce com o tamanho n da entrada no pior caso, ignorando constantes. Não mede segundos; mede tendência.

Classe	Nome	Exemplo típico
O(1)	constante	acessar `v[5]` em um vetor
O(log n)	logarítmica	busca binária
O(n)	linear	busca sequencial, somar todos os elementos
O(n log n)	linearítmica	ordenações eficientes, como merge sort
O(n²)	quadrática	dois laços aninhados sobre os mesmos dados

A ordem de crescimento, da mais lenta à mais rápida em crescimento, é O(1), O(log n), O(n), O(n log n), O(n²). Duas regras de leitura:

Descarte constantes e termos menores. Um algoritmo que faz 3n + 10 operações é O(n); um que faz n² + n é O(n²).
Laços em sequência somam; laços aninhados multiplicam. Dois laços de n passos, um depois do outro, dão O(n); um dentro do outro, O(n²).

Exercício resolvido

Que complexidade tem este trecho?

for i in range(n):
    for j in range(n):
        total += 1

O contador executa n vezes n, ou seja, n² vezes: O(n²). Com n igual a 10, são 100 execuções; com n igual a 20, 400. Dobrar a entrada quadruplica o trabalho.

Erros comuns

Aplicar busca binária em vetor desordenado: o resultado fica incorreto, pois a decisão de descartar metade deixa de valer.
Dizer que a binária é sempre mais rápida; ela depende de a lista estar ordenada e de acesso direto às posições.
Confundir pior caso com caso médio: a notação costuma se referir ao pior caso, salvo indicação.
Contar passos errado por esquecer que o intervalo é fechado (lo <= hi) e que o meio usa divisão inteira.
Achar que Big O dá o tempo exato em segundos.

Fontes e atualização

Não há norma oficial brasileira sobre algoritmos; o conteúdo segue a literatura clássica de estruturas de dados. As contagens foram obtidas executando o código em um teste, com o vetor da tabela. Detalhes como indexação a partir de 0 ou 1 dependem da linguagem ou do enunciado: confira o edital.

Próximos passos

Veja a ordenação em bubble, selection e insertion sort passo a passo.
Estude pilha, fila e lista com exemplos executados.
Reforce a base numérica em sistema binário, bits, bytes e unidades de armazenamento.