O que é mais eficiente: uma busca seqüencial ou uma busca binária? Explique.

Passo 1

O enunciado pergunta qual é mais eficiente entre busca sequencial e busca binária. O conteúdo envolve algoritmos de busca em vetores e análise de complexidade de tempo. Para resolver, precisamos entender como cada algoritmo percorre o vetor, quais pré-condições são exigidas (como ordenação) e comparar suas ordens de crescimento usando a notação assintótica.

Passo 2

Na busca sequencial, o algoritmo percorre os elementos um a um, comparando cada valor com o alvo até encontrá-lo ou até terminar o vetor. Não há pré-condição de ordenação, mas no pior caso examinamos todos os n elementos. Assim, o tempo de execução no pior caso cresce linearmente com o tamanho do vetor:
\mathrm{Tempo}_{\text{seq}}(n) = \Theta(n).

Passo 3

Na busca binária, o vetor deve estar previamente ordenado. O algoritmo compara o valor do meio do intervalo atual com o alvo e elimina metade dos elementos a cada iteração. Logo, o número máximo de comparações é da ordem de \log_{2}n, e o tempo de execução no pior caso é
\mathrm{Tempo}_{\text{bin}}(n) = \Theta(\log n).
Isso pressupõe acesso aleatório aos elementos em tempo constante.

Passo 4

Comparando as ordens de crescimento, temos
\Theta(\log n) \ll \Theta(n)\quad\text{para grandes }n.
Portanto, a busca binária é assintoticamente mais eficiente em tempo quando o vetor está ordenado e permite acesso aleatório. A busca sequencial só é vantajosa se o vetor não estiver ordenado e não compensar o custo de uma ordenação, ou em vetores muito pequenos.

Resposta

A busca binária é mais eficiente em termos de tempo assintótico \Theta(\log n) contra \Theta(n), desde que o vetor esteja ordenado e haja acesso aleatório aos elementos.

Exercícios de Livros Relacionados