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
- Um sistema de uma estufa analisa cinco leituras de umidade do solo: 19, 22, 24, 27 e 20. O algoritmo conta as leituras…
- Na montagem de um boletim digital da escola, as seções estão nesta ordem: capa, entrevista, fotos e agenda. A equipe…
- Em um aplicativo da escola, a lista de representantes da turma aparece nesta ordem: Ana, Bia, Caio, Davi e Elisa. Caio…
- Enquanto agentes de manutenção acompanham pedidos de reparo de bicicletas públicas, o painel registra os chamados em uma…
- — O livro de Marina Souza está disponível? — perguntou uma visitante ao balcão da biblioteca municipal. No computador…
- — O kit 47 já foi devolvido? — perguntou a técnica responsável pela campanha itinerante de vacinação. Antes do uso de…
🔎 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