O algoritmo de busca binária é mais eficiente que o de busca linear, para um mesmo vetor, desde que
- A)o vetor esteja ordenado.
Correta, porque a busca binária só pode ser aplicada com segurança em vetor ordenado.
- B)o algoritmo explore o processamento repetitivo.
Errada, processamento repetitivo não é a condição que torna a busca binária mais eficiente.
- C)o algoritmo trabalhe em um formato circular de repetição.
Errada, formato circular de repetição não tem relação com o princípio da busca binária.
- D)o algoritmo percorra o vetor verificando se o elemento desejado está presente.
Errada, essa descrição é justamente da busca linear, não da binária.
- E)o tamanho do vetor seja pequeno.
Errada, o tamanho pequeno do vetor até pode tornar a busca linear competitiva, mas não é a condição para a busca binária ser mais eficiente.
Gabarito: A
A busca linear vai olhando elemento por elemento, como quem passa a lista inteira sem pressa. Já a busca binária divide o problema ao meio a cada comparação, então ela corta muito trabalho - mas isso só funciona quando o vetor está ordenado. Se os dados estiverem bagunçados, não existe como saber se o item procurado ficou à esquerda ou à direita do meio, e aí a estratégia binária perde o sentido. Por isso, a eficiência maior da busca binária depende da ordenação prévia do vetor. Em termos de teoria, é o clássico contraste entre O(n) da busca linear e O(log n) da busca binária em estrutura ordenada.