ATIVIDADE I - PESQUINA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO

Prévia do material em texto

Caro, aluno,
ao longo da Unidade foram abordados: a problemática do crescimento do volume de dados;
conceitos e técnicas sobre algoritmos de busca, ordenação e armazenamento; bem como
análise de complexidade. Os referidos algoritmos são recursos importantes que possibilitam
melhor aproveitamento da grande quantidade de informação armazenada nos repositórios de
dados. Estes assuntos proporcionaram a você uma ampla visão sobre o tema, sua
aplicabilidade e importância no cenário tecnológico atual. (MANZANO, J. A. N. G.;
LOURENÇO, A. E.; MATOS, E. Algoritmos - Técnicas de Programação. 2. ed. São Paulo:
Érica, 2015.)
Com base no material que você estudou, escreva sobre algoritmos de busca sequencial e
binária, dando exemplos e buscando apresentar as diferenças.
Bons Estudos!
Antes de mais nada, devemos recapitular o que uma busca/pesquisa
faz, em sumo nada mais é que verificar a presença ou não de um
elemento em um conjunto de dados que essa busca queira achar. O que
diferencia é a forma como essa pesquisa será feita, nesse caso dos
nossos estudos será a busca Binária e Sequencial.
No caso da busca Binária é um método mais complexo e tem a exigência
que o vetor esteja ordenado, é um algoritmo um pouco mais sofisticado e
mais eficiente, mas requer que o vetor esteja ordenado pelos valores da
chave de busca, ao contrário da busca Sequencial que tanto faz se é
ordenado ou não.
O primeiro passo da busca Binária começará por examinar o item do
meio, caso ache o dado procurado a pesquisa retornada com sucesso,
caso contrário; Segundo passo é que se a chave for menor, o
procedimento é repetido na primeira metade do vetor, se a chave for maior,
o procedimento é repetido na segunda metade do vetor. Assim o processo
é repetido até que seja retornado com sucesso ou que acabe os itens do
vetor.
Abaixo um exemplo de algoritmo de busca binária:
int binaria(int a[], int indice, int esq, int dir){
while(dir>=esq){
int meio=(esq+dir)/2;
if(indice==a[meio]) return meio;
if(indice<a[meio])
dir=meio-1;
}
}
A busca Sequencial é a forma mais simples de se fazer uma pesquisa, a
partir do momento que se tem um vetor com suas informações
preenchidas, o algoritmo de busca percorre índice por índice procurando e
comparando o conteúdo o qual quer achar. A cada índice que é percorrido
tem-se um retorno de “sucesso” ou “insucesso”.
Em linhas gerais, a busca Sequencial é o algoritmo mais simples de
busca:
● Percorra todo o vetor comparando a chave com o valor de cada
posição.
● Se for igual para alguma posição, então devolva esta posição.
● Se o vetor todo foi percorrido então devolva -1.
Abaixo temos um exemplo de algoritmo de busca Sequencial em um vetor
não ordenado:
int busca(int a[], int indice, int esq, int dir){
for(int i=esq; i<=dir;i++)
if(indice==a[i] return i;)
return -1;
}