MAPA – ADSIS – ESTRUTURA DE DADOS II – 52_2024
A forma mais eficiente de efetuar pesquisa em um arranjo sem a necessidade de memórias auxiliares é a busca binária. A estratégia consiste em comparar a chave de busca (dado que estamos procurando) ao elemento do meio do arranjo (vetor). Se forem iguais, a busca terá terminado com sucesso, e o algoritmo retornará a respectiva posição na qual o elemento foi encontrado. Caso contrário, o vetor será divido em duas metades, e a pesquisa será repetida na metade “inferior”, se a chave de busca for menor do que o valor do meio do arranjo, ou na parte “superior”, se a chave de busca for maior. A cada iteração, a busca binária reduz a quantidade de possíveis candidatos pela metade. Isso faz com que a velocidade de busca seja extremamente rápida, já que, em tese, o algoritmo implementa uma heurística que elimina a necessidade de investigar porções do vetor cuja busca seria infrutífera. Observe o código-fonte a seguir que implementa a busca binária.
Linha | Código |
int buscaBinaria(int arranjo | |
, int i, int f, int chave) | |
{ | |
01
02 03 04 |
if (f >= i)
{ int meio = i + (f – i)/2; if (arranjo |
05 | meio |
06
07 08 09 |
== chave)
return meio; if (arranjo |
10
11 |
meio |
12
13 |
> chave)
return buscaBinaria(arranjo, i, meio-1, chave); |
return buscaBinaria(arranjo, meio+1, f, chave); | |
} | |
return -1; | |
} |
Responda:
- a) Caso a chave de busca seja um valor que esteja ausente dentro do arranjo, qual é o valor que a função buscaBinaria() retornará?
- b) Para que essa busca funcione, o arranjo precisa, necessariamente, estar ordenado? Se sim, explique o motivo.
- c) Para que essa busca seja rápida, é preciso aplicar ela em um arranjo estático? Se sim, explique o motivo.
- d) Imagine que essa função precisa ser invocada dentro da função main() de um programa em C. Dessa forma, escreva a linha de código (apenas uma linha) que invocaria essa função para realizar a busca em um arranjo denominado VET, que possui 10 elementos, e que a chave de busca é igual a 15.
Sua resposta deve ser enviada contendo a resposta para os quatro itens descritos acima.
ATENÇÃO: a entrega deve ser feita exclusivamente por meio de um arquivo .doc, .docx ou .pdf. Utilize o
template de entrega da atividade MAPA disponível no material da disciplina.
Antes de enviar a sua atividade, certifique-se de que respondeu a todas as perguntas e não se esqueceu de nenhum detalhe. Após o envio, não são permitas alterações. Por favor, não insista.
Orientações:
- Plágios e cópias indevidas serão penalizados com nota zero.
- As perguntas devem ser respondidas de forma adequada, ou seja, precisam ser coerentes.
- Não são permitidas correções parciais no decorrer do módulo, ou seja, o famoso: “professor, veja se minha atividade está certa?”. Isso invalida seu processo avaliativo. Lembre-se de que a interpretação da atividade também faz parte da avaliação.
- Procure sanar suas dúvidas sobre o conteúdo exigido na atividade, de modo que consiga realizar sua participação.
- Atenção ao prazo de entrega, evite o envio de atividade em cima do prazo. Evite transtornos.
Acesse nossas aulas conceituais e ao vivo. Seja participativo durante o módulo e procure sanar suas dúvidas pedagógicas junto à mediação em tempo hábil para a realização da atividade.
Olá, somos a Prime Educacional!
Nossa equipe é composta por profissionais especializados em diversas áreas, o que nos permite oferecer uma assessoria completa na elaboração de uma ampla variedade de atividades. Estamos empenhados em garantir a autenticidade e originalidade de todos os trabalhos que realizamos.
Ficaríamos muito satisfeitos em poder ajudar você. Entre em contato conosco para solicitar o seu serviço.
Aponte o celular para abrir o WhatsApp