Para resolver um problema de busca em uma lista ordenada, qual é a opção mais eficiente?
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Construir soluções computacionais de problemas de diferentes áreas do conhecimento, de forma individual e colaborativa, selecionando as estruturas de dados e técnicas adequadas, aperfeiçoando e articulando saberes escolares.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Para resolver um problema de busca em uma lista ordenada, qual é a opção mais eficiente?
- A) Busca binária
- B) Busca aleatória
- C) Busca em profundidade
- D) Busca linear
- E) Busca em largura
✅ Resposta correta: alternativa A
Resolução passo a passo
- Identifique o contexto. A questão pergunta qual método de busca é mais eficiente para encontrar um elemento em uma lista já ordenada.
- Pense no funcionamento da busca binária. Ela compara o valor procurado com o elemento do meio da lista. Se forem diferentes, descarta a metade em que o valor certamente não está e repete o processo na metade restante.
- Calcule o custo. A cada comparação, o espaço de busca cai pela metade. Em uma lista de n elementos, o número máximo de comparações é aproximadamente log2(n), ou seja, complexidade de tempo O(log n). Por exemplo, uma lista de 1.024 elementos exige, no máximo, cerca de 10 comparações.
- Compare com as demais alternativas. A busca linear (D) também funciona em listas ordenadas, mas percorre elemento por elemento, com complexidade O(n). A busca aleatória (B) sorteia posições ao acaso, sem aproveitar a ordenação, e pode demorar muito. A busca em profundidade (C) e a busca em largura (E) são estratégias de percurso em grafos e árvores, não são o método padrão para localizar um valor em uma lista ordenada.
- Conclusão. A busca binária é a opção mais eficiente para o problema proposto, pois explora a ordenação da lista para reduzir o espaço de busca pela metade a cada passo. O gabarito oficial A está correto.
💡 Dica: Considere que a lista ordenada permite descartar metade dos elementos a cada etapa.
Alternativa por alternativa
Como a lista está ordenada, a busca binária pode descartar metade dos elementos a cada etapa, reduzindo o número de comparações necessárias.
O aluno pode imaginar que escolher posições ao acaso é uma estratégia rápida, como se a sorte ajudasse a encontrar o valor mais cedo. Não percebe que a busca aleatória ignora a ordenação e pode repetir verificações.
O aluno pode associar qualquer método de busca à busca em profundidade, que é muito conhecida em estudos de grafos. Não percebe que ela é um percurso de grafos e árvores, sem relação direta com a eficiência em listas ordenadas.
O aluno pode achar que a busca linear é a mais eficiente por ser simples e direta, sem considerar que ela não aproveita a ordenação da lista. No pior caso, percorre todos os n elementos.
Por que engana: Escolher busca linear por ser um método conhecido, sem considerar que a ordenação permite reduzir pela metade o espaço de busca em cada etapa.
O aluno pode confundir a busca em largura com um método geral de busca, por ser estudada junto com a profundidade. Não percebe que ela explora grafos nível a nível e não tira proveito da ordenação de uma lista.
Raio-X da questão
Busca binária em lista ordenada
avaliacao
Algoritmos de busca em listas · Ordenação de elementos
Revise a diferença de eficiência entre busca binária e busca linear em listas ordenadas.
Escolher busca linear por ser um método conhecido, sem considerar que a ordenação permite reduzir pela metade o espaço de busca em cada etapa.
ciencia_tecnologia
tomada_decisao
abstrato
Questões parecidas com resolução
- Ao criar um algoritmo que resolve um problema de busca em uma lista de produtos, qual a abordagem mais eficiente se a…
- Qual dos seguintes algoritmos é mais apropriado para buscar um valor em uma lista ordenada?
- Ao resolver um problema de busca em uma lista, qual abordagem recursiva pode ser utilizada?
- Para reduzir o número de comparações ao buscar um elemento em um vetor já ordenado, qual algoritmo de busca é mais…
- Em um projeto de programação, como se pode otimizar a busca de informações em uma lista de dados que já está ordenada?
- Uma biblioteca pública mantém um cadastro digital com 4.096 nomes de usuários, organizados em ordem alfabética. O…
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog