Pesquisa - Atividade 1

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!
Podemos perceber que o aumento significativo no volume de dados, com isso para que as tarefas sejam realizadas, com agilidade e eficiências é necessário que algoritmos otimizados sejam utilizados. Seja na estratégia linear quanto na sequencial binaria, onde na pesquisa linear o vetor será percorrido até encontrar a chave onde encontra-se o valor retornando-o, caso não seja possível informará o não sucesso da busca ali realizada.
Ex: num vetor que possui os números de 1 a 10 ao pesquisar o número 9 a pesquisa irá percorrer do número 1 até o 9 e retornar esse valor. Caso seja solicitado algo que não esteja nesse vetor informará que não obteve sucesso.
Já a pesquisa binária trata-se de um algoritmo mais eficiente, pois ele presume que o valor solicitado se encontra próximo do meio do vetor, sendo assim, ele divide o vetor em dois eliminando metade dele neste primeiro momento para fazer a busca, caso não encontre ele pega a outra metade e repete o mesmo processo até encontrar a chave ou até percorrer todos os valores sem êxito.
Antes de tudo devemos recapitular o que uma busca/pesquisa faz, 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 de como essa 
pesquisa será feita, no nosso caso de estudo é a busca Binária e a Sequencial.
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 
"sucesso" ou "insucesso".
Aqui 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;
 }
No caso da Busca Binária é um método um pouco mais complexo e tem 
a exigência que o vetor esteja ordenado, ao contrário da busca sequencial que 
tanto faz se é ordenado ou não. A busca binária funciona da seguinte forma: 
Primeiro passo é a comparação do meio do vetor, 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.
E aqui 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;