Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — COPERVE - UFSC 2018
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
qq326393
Banca
COPERVE - UFSC
Órgão
UFSC
Ano
2018
Nível
Superior
Cargo
COPERVE - - Analista de Tecnologia da Informação
Considere o problema de pesquisar por um número em um array ordenado contendo dez números. Se for utilizado o método da pesquisa binária, qual é o menor número de comparações que permite concluir que um número não está presente no array?
A4
B5
C2
D3
E6
Revelar gabarito e comentário▾
GabaritoD — 3
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Busca binária – número mínimo de comparações para conclusão de ausência
Gabarito: letra D (3). Em um array ordenado com 10 elementos, o menor número de comparações necessário para concluir que um número não está presente é 3. Isso ocorre quando o valor procurado é menor do que o menor elemento do array (ou, analogamente, quando o alvo recai na primeira posição após sucessivas divisões). O algoritmo de busca binária realiza comparações com os elementos do meio, reduzindo o espaço de busca pela metade a cada passo.
Para entender, considere índices de 0 a 9. A primeira comparação é com o elemento do meio (índice 4). Se o alvo for menor, a busca continua na metade esquerda (índices 0 a 3). A segunda comparação é com o meio dessa sublista (índice 1). Se ainda for menor, a busca vai para os índices 0 a 0. A terceira comparação é com o elemento do índice 0. Sendo menor, não há mais elementos e a conclusão de ausência é alcançada após 3 comparações. Esse é o melhor cenário para uma busca mal-sucedida.
A alternativa A (4) corresponde ao pior caso (por exemplo, quando o alvo é maior que o último elemento). As alternativas B (5), C (2) e E (6) não condizem com o funcionamento do algoritmo.
1Compara com índice 4 (meio)
2Alvo menor → metade esquerda (0-3)
3Compara com índice 1 (meio)
4Alvo menor → metade esquerda (0-0)
5Compara com índice 0
6Alvo menor → ausência concluída
LEVEL · soulevel.com.br
NÃO CAIA NESSA!
A banca explora a confusão entre o pior caso (4 comparações) e o melhor caso para ausência (3). O candidato que decora apenas a fórmula ⌊log₂ n⌋+1 = 4 marca errado. A chave é perceber que o menor número de comparações para concluir a ausência é obtido nos caminhos mais curtos da árvore de busca.