Questão de Tecnologia da Informação · FGV TCE-TO 2022 (nº 36)

A busca binária funciona dividindo o array ordenado ao meio a cada comparação, descartando metade dos candidatos restantes. Como o tamanho do problema é reduzido pela metade a cada passo, o número máximo de comparações (pior caso) é o número de vezes que você pode dividir $N$ por 2 até sobrar 1 elemento, que é exatamente $\log_2 N$.

• (A) Correta: A cada acesso, o intervalo de busca é reduzido à metade; após $k$ acessos, restam $N/2^k$ elementos. O pior caso termina quando $N/2^k = 1$, logo $k = \log_2 N$ — esta é a definição de complexidade logarítmica.
• (B) Incorreta: $\log_2 N \cdot N$ seria a complexidade de fazer $N$ buscas binárias separadas, ou de um algoritmo que percorre todos os elementos e ainda aplica uma busca binária — não é o custo de uma única busca.
• (C) Incorreta: $N$ seria o custo de uma busca linear, que examina cada elemento do início ao fim; a busca binária nunca precisa visitar todos os elementos, pois descarta metade a cada passo.
• (D) Incorreta: $N/2$ é o número médio de acessos de uma busca linear (ou o primeiro acesso da binária, que olha o meio), mas não o pior caso da binária, que é sempre logarítmico.
• (E) Incorreta: $N^2$ seria típico de algoritmos de ordenação ingênuos (como bubble sort) ou de buscas em matrizes bidimensionais sem ordenação; não tem relação com a busca binária.

Armadilha do distrator mais tentador (C): A banca aposta no aluno que confunde "busca em array ordenado" com "busca sequencial". A pegadinha é achar que, por ser um array, você precisa olhar todos os elementos — mas a ordenação é justamente o que permite pular metade dos elementos a cada comparação, garantindo o custo logarítmico.