ATIVIDADE-01 - Pesquisa, Ordenação e Técnicas de Armazenamento

Prévia do material em texto

ATIVIDADE 01
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 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 encontrar. 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 se quer encontrar. A cada índice que se percorrido se tem um retorno de sucesso ou insucesso.
	A seguir tem-se o exemplo de algoritmo de busca Sequencial em um vetor não ordenado: 
	int busca (int a[], inte 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 e 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 está ordenado ou não. A busca Binária funciona da seguinte forma:
	No Primeiro passo é feita a comparação do meio do vetor. Caso o dado procurado seja encontrado a pesquisa retorna com sucesso, caso contrário parte para o segundo passo.
	No segundo passo, 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 se tenha um retorno de sucesso ou até que acabe os itens do vetor. Seguindo a ideia de dividir para conquistar.
Segue 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;
			eles esq=meio+1
		}
		return-1
	}