Escreva um algoritmo em pseudocódigo que, dado um vetor ordenado de dados inteiros e uma variável alvo, use…

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

Questões parecidas com resolução

• Explique como funciona um algoritmo de busca binária e sua aplicação na ordenação de dados em um vetor.
• Projete, em pseudocódigo, um algoritmo que receba um vetor A[0..n-1] de inteiros e um inteiro alvo t, e retorne dois…
• Projete um algoritmo em pseudocódigo que receba um vetor de comprimento ímpar contendo dados numéricos e retorne a…
• O que caracteriza um algoritmo de busca binária?
• Projete um algoritmo em pseudocódigo que, dado um vetor de números inteiros com tamanho par, percorra o vetor em pares…
• Projete um algoritmo em pseudocódigo que, dado um vetor V de n inteiros e um inteiro k, determine se existem índices i <…

Todas as questões de Programação - Algoritmos clássicos