A1 PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO

Prévia do material em texto

A1 - PESQUISA, ORDENAÇÃO E TÉCNICAS DE ARMAZENAMENTO 
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! 
 
RESPOSTA: 
 
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; 
}