No pior caso, o número de acessos numa busca binária num array ordenado, com N chaves distintas, é da ordem de:
- A)log2 N
Correta: a busca binaria reduz o espaco de busca pela metade a cada passo, então o pior caso e O(log2 N).
- B)log2 N . N
Errada: misturar log2 N com N nao faz sentido para a complexidade da busca binaria, que nao cresce multiplicando esses termos.
- C)N
Errada: O(N) e a complexidade de busca linear, nao de busca binaria em array ordenado.
- D)N/2
Errada: N/2 pode lembrar uma unica reducao pela metade, mas nao representa o numero total de acessos da busca binaria.
- E)N2
Errada: O(N2) e muito maior do que o comportamento real da busca binaria, que e logaritmico.
Gabarito: A
Na busca binária, voce nao sai olhando elemento por elemento como numa busca linear. A ideia e simples e elegante: a cada comparacao, voce elimina metade do array ordenado. Se o primeiro teste nao resolver, o espaco de busca cai de N para N/2, depois para N/4, depois para N/8, e assim por diante. Isso faz o numero de acessos crescer muito devagar, bem no ritmo de uma funcao logaritmica. No pior caso, a busca continua dividindo o problema ate restar um unico elemento ou ate concluir que a chave nao esta no array. O total de etapas fica proporcional a log2 N, porque voce precisa de aproximadamente quantas divisões por 2 sao necessarias para chegar a 1. Em notacao assintotica, isso e O(log N), e nao O(N), que seria o comportamento de uma busca sequencial. Por isso, a alternativa A esta correta: o numero de acessos na busca binaria, no pior caso, e da ordem de log2 N. Se a questao fala em acessos, comparacoes ou passos, a ideia central e a mesma: cada passo corta o problema pela metade. E a banca costuma gostar exatamente dessa troca de escalas, em que um algoritmo parece rapido nao por magia, mas porque vai afinando o alvo em ritmo logaritmico.