Um algoritmo de busca binária em uma lista ordenada de n elementos reduz o espaço de busca pela metade a cada…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar o comportamento dos algoritmos no que diz respeito ao consumo de recursos como tempo de execução, espaço de memória e energia, entre outros.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Um algoritmo de busca binária em uma lista ordenada de n elementos reduz o espaço de busca pela metade a cada passo. Qual é a ordem de crescimento do número de comparações em função de n?
- A) A ordem de crescimento é O(n) — linear.
- B) A ordem de crescimento é O(1) — constante.
- C) A ordem de crescimento é O(n log n).
- D) O(log n) — ordem logarítmica
- E) A ordem de crescimento é O(n^2) — quadrática.
✅ Resposta correta: alternativa D
Resolução passo a passo
- A busca binária divide o espaço de busca ao meio a cada comparação. Se a lista tem n elementos, após o primeiro passo restam cerca de n/2, depois n/4, n/8, e assim por diante.
- O número de passos k até restar apenas 1 elemento satisfaz n/2^k = 1, ou seja, 2^k = n, logo k = log2(n).
- Como cada passo faz um número constante de comparações, o número total de comparações cresce proporcionalmente a log n. Portanto a ordem de crescimento é O(log n), alternativa D, que coincide com o gabarito oficial.
- Por que as outras estão erradas: A) O(n) descreve a busca linear, que percorre a lista elemento por elemento; B) O(1) significaria número fixo de comparações, o que a busca binária não garante; C) O(n log n) é típico de algoritmos de ordenação eficientes, não de buscas; E) O(n^2) é o custo de algoritmos de ordenação simples, muito maior que o da busca binária.
- Conclusão: a alternativa D está correta, pois a redução pela metade a cada passo gera crescimento logarítmico.
💡 Dica: Considere a definição de complexidade de algoritmos.
Alternativa por alternativa
O aluno pensa que, como a lista precisa ser percorrida, cada elemento deve ser visitado, o que vale para a busca sequencial e não para a binária.
Por que engana: Confundir a ordem de crescimento da busca binária com a busca linear, acreditando que ambas têm complexidade O(n).
O aluno acredita que a busca binária encontra o elemento com um número fixo de comparações, talvez por achar que basta olhar o meio da lista.
O aluno associa o termo logaritmo a algoritmos de ordenação como merge sort e combina essa complexidade com a linearidade da leitura dos dados.
A cada comparação o espaço é dividido por 2; o número de etapas cresce proporcionalmente a log2 n, portanto complexidade O(log n).
O aluno supõe que algoritmos com dois laços aninhados ou comparações entre pares de elementos são típicos de qualquer busca, sem considerar a redução pela metade do espaço.
Raio-X da questão
busca binária
avaliacao
análise de algoritmos · notação assintótica
Revisar a complexidade de algoritmos de busca.
Confundir a ordem de crescimento da busca binária com a busca linear, acreditando que ambas têm complexidade O(n).
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Qual é a principal vantagem de usar algoritmos de busca binária sobre busca linear em listas ordenadas?
- Em uma árvore binária de busca balanceada com n nós, qual a complexidade temporal do algoritmo de busca em termos de n?
- Em uma atividade prática, duas estratégias de busca em listas de nomes foram registradas: busca linear (desordenada) e…
- O que caracteriza um algoritmo de busca binária?
- Uma escola guarda os números de matrícula em um vetor ordenado. Para encontrar uma matrícula, o programa pode comparar o…
- 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