Questão de Algoritmos e Estrutura de Dados — Algoritmos de Busca — FCC 2016
Algoritmos e Estrutura de Dados›Algoritmos de Busca
Código
fc033339
Banca
FCC
Órgão
TRT - 14ª Região (RO e AC)
Ano
2016
Nível
Superior
Cargo
Analista Judiciário - Tecnologia da Informação
Dada uma coleção de n elementos ordenados por ordem crescente, pretende-se saber se um determinado elemento x existe nessa coleção. Supondo que essa coleção está implementada como sendo um vetor a[0...n-1] de n elementos inteiros, utilizando-se um algoritmo de pesquisa binária, o número de vezes que a comparação x==a[i] será executada, no pior caso, é calculada por
An/2.
Bn−1.
C√n.
Dlog₂(n).
En−=2.
Revelar gabarito e comentário▾
GabaritoD — log₂(n).
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”.
Pesquisa binária: número de comparações no pior caso
Gabarito: letra D. Na pesquisa binária, a cada iteração o vetor é dividido ao meio, descartando-se metade dos elementos. No pior caso (elemento não encontrado ou encontrado na última iteração), o número de comparações da forma x == a[i] é igual ao número de iterações, que é aproximadamente log₂(n). Isso porque o algoritmo reduz o intervalo de busca pela metade até restar um único elemento.
A pesquisa binária é um clássico algoritmo de decremento e conquista. Dado um vetor ordenado de n elementos, o algoritmo compara o elemento buscado x com o elemento do meio a[meio]. Se for igual, a busca termina; se x for menor, busca-se na metade esquerda; se maior, na metade direita. O pior caso ocorre quando o elemento não está no vetor ou está na posição extrema, exigindo log₂(n) comparações (arredondado para cima).
1Vetor ordenado de n elementos
2Compara x com a[meio]
3Descarta metade do vetor
4Repete até 1 elemento restar
5Total: log₂(n) comparações
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
n/2 é o número médio de comparações na busca sequencial (linear) se o elemento estiver presente, não na pesquisa binária. Confunde o candidato com a média da busca linear.
Alternativa B — ❌ Incorreta
n−1 corresponde ao pior caso da busca sequencial (elemento no final ou ausente). A pesquisa binária é muito mais eficiente, com complexidade logarítmica.
Alternativa C — ❌ Incorreta
√n não se relaciona com o número de comparações da pesquisa binária. Talvez remeta a algum algoritmo de busca em grade, mas não é o caso.
Alternativa D — ✅ Correta ⟵ GABARITO
log₂(n). Exato. A pesquisa binária, no pior caso, realiza ⌊log₂(n)⌋ + 1 comparações (ou ⌈log₂(n+1)⌉), que é aproximadamente log₂(n). Cada iteração faz uma comparação x == a[i], portanto o número de comparações é o próprio número de iterações.
Alternativa E — ❌ Incorreta
n−=2 é um erro de digitação ou expressão inválida. Não representa nenhuma métrica conhecida. Possivelmente tentou representar n/2 ou n-2, mas ambas estão incorretas.
NÃO CAIA NESSA!
A banca explora a confusão entre busca binária e busca sequencial. O candidato desatento pode marcar n/2 (alternativa A) ou n-1 (alternativa B), que são típicos da busca linear. Lembre-se: busca binária em vetor ordenado → O(log n); busca sequencial → O(n) no pior caso.