Questão de Algoritmos e Estrutura de Dados — Algoritmos — FCC 2018
Algoritmos e Estrutura de Dados›Algoritmos
Código
fc044545
Banca
FCC
Órgão
DPE-AM
Ano
2018
Cargo
Assistente Técnico de Defensoria - Programador
Considere que na Defensoria há uma lista ordenada com o nome de 1000 cidadãos amazonenses. Utilizando o método de pesquisa binária para localizar o nome de um destes cidadãos, serão necessárias, no máximo,
A1.000 comparações.
B10 comparações.
C500 comparações.
D200 comparações.
E5 comparações.
Revelar gabarito e comentário▾
GabaritoB — 10 comparações.
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 Máximo de Comparações
Gabarito: letra B. A pesquisa binária em uma lista ordenada de 1000 elementos realiza, no pior caso, no máximo 10 comparações. Isso porque o número máximo de comparações necessárias é dado por ⌊log₂ n⌋ + 1, onde n é o tamanho da lista. Para n = 1000, log₂(1000) ≈ 9,97 → ⌊9,97⌋ = 9 → 9 + 1 = 10.
A pesquisa binária funciona dividindo repetidamente o intervalo de busca pela metade. A cada comparação, o espaço de busca é reduzido à metade. Após k comparações, o maior número de elementos que ainda podem ser distinguidos é 2ᵏ. Assim, para garantir a localização de qualquer elemento, precisamos de 2ᵏ ≥ n. A menor potência de 2 que atende 1000 é 2¹⁰ = 1024, portanto são necessárias 10 comparações no máximo.
PEGA ESSA DICA!
Decore a fórmula: para n elementos, o número máximo de comparações da busca binária é ⌈log₂(n+1)⌉ ou ⌊log₂ n⌋ + 1. Veja potências de 2: 2¹⁰ = 1024 > 1000, então 10 comparações. Se fosse 1024, seriam 10 também; para 1025, seriam 11.
Alternativa A — ❌ Incorreta
1.000 comparações corresponde ao pior caso da busca linear (sequencial), não da binária. Na busca binária, o número máximo é logarítmico, não linear.
Alternativa B — ✅ Correta ⟵ GABARITO
Conforme demonstrado, 10 é o teto máximo para 1000 elementos. A cada etapa reduz-se o intervalo à metade, e 10 passos bastam para cobrir todo o conjunto.
Alternativa C — ❌ Incorreta
500 comparações seria o número médio da busca linear em uma lista de 1000 (pior caso 1000, médio 500). Não tem relação com a complexidade logarítmica da busca binária.
Alternativa D — ❌ Incorreta
200 não corresponde a nenhuma potência de 2 próxima. Seriam necessárias cerca de 8 comparações para 200 elementos, não para 1000.
Alternativa E — ❌ Incorreta
5 comparações só seriam suficientes para até 2⁵ = 32 elementos. Para 1000, o mínimo necessário é 10.