Escreva um algoritmo em pseudocódigo que, dado um vetor ordenado de dados inteiros e uma variável alvo, use…
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
Escreva um algoritmo em pseudocódigo que, dado um vetor ordenado de dados inteiros e uma variável alvo, use busca binária para retornar o índice do alvo ou -1 se não existir; explique a lógica e a complexidade.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
baixo <- 0 alto <- n-1 enquanto baixo <= alto faça meio <- (baixo + alto) // 2 se A[meio] = alvo então retornar meio se A[meio] < alvo então baixo <- meio + 1 senão alto <- meio - 1 fim enquanto retornar -1 Lógica: divide repetidamente o intervalo ao meio até achar o alvo ou esgotar. Complexidade temporal: O(log n); espacial: O(1).
Explicação
O algoritmo utiliza a estratégia de divisão e conquista, reduzindo pela metade o espaço de busca a cada iteração, o que permite localizar o alvo de forma eficiente. A complexidade temporal O(log n) reflete essa redução exponencial do espaço de busca, enquanto a complexidade espacial O(1) indica que o algoritmo utiliza uma quantidade constante de memória, independentemente do tamanho do vetor. Essa abordagem é ideal para vetores ordenados, garantindo uma busca rápida e eficaz.
Raio-X da questão
busca binária
avaliacao
vetores e arrays · algoritmos de busca
Revisar a lógica da busca binária e sua complexidade.
O aluno pode confundir a lógica da busca binária com a busca linear, resultando em um algoritmo ineficiente.
ciencia_tecnologia
pensamento_critico
cientifico
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