Você sabia que durante o processo de busca de dados em um arranjo linear é possível "cortar caminho" para deixar de vasculhar regiões do vetor que provavelmente não contenham a resposta para a busca? Quando se realiza a busca binária, pode ser muito mais rápido encontrar a posição de um elemento em um arranjo, ou mesmo, dizer se o elemento está ausente no vetor. OLIVEIRA, Pietro Martins de; LEON, Rogério de. Estrutura de Dados II. Maringá-PR, Unicesumar, 2019. Observe o pseudocódigo a seguir:
//Função de Busca Binária
int BuscaBinaria(int vec[], int arg, int tam){
int menor, maior, meio;
menor = 0;
maior = tam-1;
while (menor <= maior){
meio = (menor + maior)/2;
if (arg == vec[meio]){
return(meio);
}
if(arg < vec[meio]){
maior = meio - 1;
}
else {
menor = meio + 1;
}
}
return(-1);
}
Com base no código-fonte apresentado acima, avalie as afirmações a seguir:
I. A fórmula para identificar a posição do meio do arranjo está incorreta no corpo da função BuscaBinaria() acima. II. Em caso de elemento ausente, este algoritmo irá retornar o valor inteiro -1. III. Este algoritmo poderia ser implementado de forma recursiva. É correto o que se afirma em:
Alternativas
Alternativa 1:
I, apenas. Alternativa 2:
I e II, apenas. Alternativa 3:
I e III, apenas. Alternativa 4:
II e III, apenas. Alternativa 5:
I, II e III
Soluções para a tarefa
A função de BuscaBinaria() descrita nessa tarefa, retorna o valor inteiro -1, em caso de que não encontre o elemento no vetor. Este algoritmo poderia ser implementado de forma recursiva. A alternativa 5 é a resposta certa.
Busca binária
A busca binária é um algoritmo eficiente para encontrar um elemento em uma lista ordenada de elementos. Ele funciona dividindo repetidamente a parte da lista que poderia conter o item pela metade, até que as localizações possíveis sejam reduzidas a apenas uma.
Notem que é uma tarefa principal repetida varias vezes ate achar o elemento dentro de um vetor, ele pode ser implementado recursivamente, que tem como condição de parada se achar o elemneto ou se não achar retorna -1.
Este algoritmo é tambem conhecido como algoritmo de Divisão e Conquista resultando em tempo de execução O(log n), sendo n o tamanho do vetor.
Supondo que tenhamos o vetor A. O vetor A tem cinco elementos.
A = [10,3,50,60,7]
Definindo as variavels de acordo com o algoritmo na tarefa, temos as variables,
menor = 0
tam = 5
maior = 4
meio = 2
A[2] é o valor do meio do vetor, no caso é 50. Logo a fórmula para identificar a posição do meio do arranjo está correta.
Se quiser aprofundar no algoritmo de busqueda binaria, pode visitar https://brainly.com.br/tarefa/26079129
#SPJ2
Sabendo dos conceitos de busca binária, pode-se afirmar que realizando a programação correta, temos que:
- para a função de BuscaBinaria() a qual é descrita na atividade, o valor inteiro retorna a -1 (caso não encontre o elemento desejado no vetor).
- Ademais, o algoritmo pode ser implementado de forma recursiva (processo de repetição).
Portanto, conclui-se que alternativa correta que deve ser assinalada é a alternativa 5 ( II e III, apenas.)
O que é busca binária?
A busca binária ou pesquisa binária é um algoritmo que sempre busca em que vetores que segue o paradigma de divisão. Ademais, a busca parte do pressuposto de que o vetor está ordenado e que realiza sucessivas divisões de busca comparando o elemento buscado com o elemento no meio do vetor.
Saiba mais sobre busca binária em;
brainly.com.br/tarefa/1072771
#SPJ1
