Questão de Algoritmos e Estrutura de Dados — Algoritmos — Instituto Fênix 2024
Algoritmos e Estrutura de Dados›Algoritmos
Código
qg310156
Banca
Instituto Fênix
Órgão
Prefeitura de São José do Cerrito - SC
Ano
2024
Nível
Superior
Cargo
Analista de Sistemas
Considerando os conceitos de algoritmos de busca, analise as assertivas sobre a busca binária.I. A busca binária é mais eficiente que a busca linear para listas desordenadas.II. A busca binária opera dividindo repetidamente pela metade a porção da lista que pode conter o item de busca, até que este seja encontrado ou que a porção se reduza a zero.III. Para aplicar a busca binária, a lista deve estar ordenada.Das assertivas, pode-se afirmar que:
AApenas I e II são verdadeiras.
BApenas II e III são verdadeiras.
CTodas são verdadeiras.
DApenas III é verdadeira.
Revelar gabarito e comentário▾
GabaritoB — Apenas II e III são verdadeiras.
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
Gabarito: alternativa B (apenas II e III são verdadeiras). A busca binária é um algoritmo eficiente, mas exige que a lista esteja previamente ordenada (assertiva III). Ela funciona dividindo repetidamente o intervalo de busca pela metade (assertiva II). Já para listas desordenadas, a busca binária não pode ser aplicada diretamente – a busca linear é mais adequada (assertiva I falsa).
Assertiva
Descrição
Verdadeira?
Justificativa
I
A busca binária é mais eficiente que a busca linear para listas desordenadas.
❌ Falsa
A busca binária exige lista ordenada; para listas desordenadas, a busca linear é a adequada.
II
A busca binária opera dividindo repetidamente pela metade a porção da lista que pode conter o item de busca, até que este seja encontrado ou que a porção se reduza a zero.
✅ Verdadeira
Essa é a definição clássica do funcionamento do algoritmo.
III
Para aplicar a busca binária, a lista deve estar ordenada.
✅ Verdadeira
A ordenação é pré-requisito fundamental para o algoritmo funcionar corretamente.
Busca binária: Pré-requisito (Lista ordenada); Funcionamento (Divide pela metade, Compara com o centro, Reduz intervalo até zero); Complexidade (O(log n) no caso médio); Limitação (Não serve para lista desordenada)
Assertiva I — ❌ Falsa
A afirmação diz que a busca binária é mais eficiente que a linear para listas desordenadas. Isso é incorreto: a busca binária depende da ordenação para funcionar. Em listas desordenadas, não é possível realizar a divisão binária, pois não se sabe em qual metade o elemento pode estar. A busca linear, embora O(n), é a única que funciona sem ordenação. Portanto, a assertiva I é falsa.
Assertiva II — ✅ Verdadeira
A descrição está correta: a busca binária reduz o espaço de busca pela metade a cada iteração, comparando o elemento alvo com o valor central do intervalo, até encontrá-lo ou até que o intervalo se reduza a zero. Essa é a essência do algoritmo.
Assertiva III — ✅ Verdadeira
Sim, a condição fundamental para aplicar a busca binária é que a lista esteja ordenada (crescente ou decrescente). Sem essa ordenação, o algoritmo não pode garantir a correta localização do elemento.
Conclusão: apenas as assertivas II e III são verdadeiras, o que corresponde à alternativa B.
PEGA ESSA DICA!
Lembre-se da tríade da busca binária: (1) lista ordenada, (2) divisão pela metade, (3) complexidade O(log n) no caso médio. A busca linear serve para qualquer lista, mas é O(n). Na prova, fique atento à palavra “desordenada” – se aparecer, a busca binária não se aplica.