Para reduzir o número de comparações ao buscar um elemento em um vetor já ordenado, qual algoritmo de busca é…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Utilizar algoritmos clássicos de manipulação sobre listas.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Para reduzir o número de comparações ao buscar um elemento em um vetor já ordenado, qual algoritmo de busca é mais adequado?
- A) Busca em largura (BFS) para encontrar X em vetores.
- B) Busca aleatória que tenta encontrar X em posições quaisquer.
- C) Busca em profundidade (DFS) para pesquisar por X.
- D) Busca sequencial (linear search) para todos os vetores.
- E) Busca binária (binary search)
✅ Resposta correta: alternativa E
Resolução passo a passo
- A questão pergunta qual algoritmo reduz o número de comparações ao buscar um elemento em um vetor já ordenado. Resolvendo por conta própria: a ideia central é aproveitar a ordenação para descartar grandes partes do vetor a cada comparação.
- A busca binária faz exatamente isso. Compara o elemento buscado com o meio do vetor; se for menor, descarta a metade da direita, se for maior, descarta a metade da esquerda. Repete o processo sobre a metade restante. Com n elementos, o número de comparações no pior caso cai para aproximadamente log2(n), bem menor que n. Portanto, a alternativa E está correta.
- Comparando com o gabarito oficial (E), há concordância.
- Por que as outras estão erradas:
- A) A busca em largura (BFS) é um algoritmo para percorrer grafos ou árvores por níveis, não é a técnica padrão para localizar um valor em um vetor ordenado.
- B) A busca aleatória sorteia posições ao acaso e não aproveita a ordenação, podendo exigir muitas comparações.
- C) A busca em profundidade (DFS) também é um método de percurso de grafos e árvores e não explora a ordenação do vetor.
- D) A busca sequencial percorre o vetor elemento por elemento, podendo exigir até n comparações, e justamente não aproveita a ordenação para reduzir comparações.
💡 Dica: Considere os algoritmos de busca mais eficientes para vetores ordenados.
Alternativa por alternativa
O aluno associa qualquer busca sistemática a BFS, sem perceber que a largura é uma estratégia de percurso de grafos e não de localização em vetores ordenados.
O aluno imagina que sortear posições ao acaso pode ser eficiente, ignorando que a aleatoriedade não usa a informação de ordenação e pode repetir ou desperdiçar comparações.
O aluno confunde busca em profundidade, um método de exploração de grafos e árvores, com uma técnica de pesquisa em estruturas lineares ordenadas.
O aluno pensa que a busca sequencial é a opção universal e esquece que, em vetor ordenado, ela não aproveita a ordem e faz até n comparações.
Por que engana: Confundir busca binária com busca sequencial, aplicando a última em vetores ordenados.
A busca binária divide repetidamente o espaço de busca ao meio, reduzindo o número de comparações para O(log n) em vetores ordenados.
Raio-X da questão
algoritmo de busca
avaliacao
algoritmo de busca · vetores ordenados
Revisar os algoritmos de busca em vetores ordenados, como busca binária.
Confundir busca binária com busca sequencial, aplicando a última em vetores ordenados.
ciencia_tecnologia
tomada_decisao
abstrato
Questões parecidas com resolução
- Qual dos seguintes algoritmos é mais apropriado para buscar um valor em uma lista ordenada?
- Para resolver um problema de busca em uma lista ordenada, qual é a opção mais eficiente?
- Uma escola guarda os números de matrícula em um vetor ordenado. Para encontrar uma matrícula, o programa pode comparar o…
- Ao criar um algoritmo que resolve um problema de busca em uma lista de produtos, qual a abordagem mais eficiente se a…
- Qual é a principal vantagem de usar algoritmos de busca binária sobre busca linear em listas ordenadas?
- 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