Resumo_BuscaBinária

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Resumo Busca Binária:
*********************************************************************************
OBS: Essa matéria cai somente na P2!
*********************************************************************************
- Antes de tudo, vamos relembrar como era feita a busca em Prog 1:
Exemplo: Queremos buscar um determinado valor (chave) num vetor de inteiros.
int busca (int v[], int n, int chave){
 int i;
 for(i=0;i<n;i++){
 if(v[i] == chave)
 return i;
 }
 return -1;
}
OBS: Essa é a busca linear, pois pra achar um determinado elemento, a >>ÚNICA<< forma é passando por cada elemento do vetor em sequência!
Desvantagem: Imagina um vetor de 300 milhões de posições e queremos achar um número que está no final....É, vai demorar um pouco. D:
E percebe que quanto maior o vetor, vai piorando cada vez mais a situação? x.x
Então a >> Busca Binária << foi criada pra resolver esse problema e agilizar todas as buscas! Dessa forma, buscas que iam levar minutos, levam segundos! 
A única desvantagem é que esse tipo de busca só funciona em vetores >>ORDENADOS<<!
Se o enunciado de uma P2 pedir pra fazer uma busca (Mesmo se não especificar, é a Binária!) e se o vetor não estiver ordenado, o primeiro passo é ordenar!
OBS: Nesse resumo não vou falar sobre ordenação pra não misturar os assuntos, dúvidas quanto a isso, só dar uma lida no bloco "Resumo_Ordenação".
Então pra todos os exemplos desse bloco, vamos considerar que o vetor já está ordenado, ok? :)
--------------------------------------//-----------------------------------------
- Busca Binária:
Ex: Queremos buscar um determinado valor num vetor de inteiros.
int busca (int v[], int n, int chave){
	int ini, fim, meio;
	ini = 0;
	fim = n-1;
	while(ini <= fim){
		meio = (ini + fim)/2;
		if(chave == v[meio]) return meio;
		else if(chave < v[meio])
			fim = meio -1;
		else ini = meio + 1;
	}
	return -1;
}
Primeiro atribuimos uma variável no começo do vetor (ini), uma para o final do vetor (fim) e outra variável que vai representar o meio do vetor.
A grande vantagem da busca binária é que a cada tentativa de achar a chave, o vetor é dividido em duas partes! (Vamos chamar de Primeira e Segunda metade) 
meio = (ini + fim)/2; 
E logo em seguida, dependendo do resultado da comparação (se for maior ou menor que o elemento atual do vetor), uma das metades será descartada! Reduzindo o tamanho do vetor pela metade! Por isso a busca é muitooo mais rápida que a linear! :D
*********************************************************************************
Regra Importante: (De acordo com o resultado da comparação)
- Se o que procuramos é menor, ou seja, vem >>ANTES<< do elemento atual do vetor: 
 
Descartamos a segunda metade do vetor! fim = meio - 1;
- Se o que procuramos vem >>DEPOIS<< do elemento atual do vetor: 
Descartamos a primeira metade do vetor! ini = meio + 1;
OBS: Isso vale para >>TODA<< Busca binária! Nunca muda! Decore ou entenda essa regra urgentemente! =D
********************************************************************************* 
Se num desses passos a variável 'ini' ficar maior que o 'fim', não faz sentido continuar a busca, pois isso quer dizer que o elemento chave >> NÃO << foi encontrado! Por isso while(ini <= fim) é justamente a condição pra repetição continuar. 
Se caso o elemento chave não for encontrado, a busca deve retornar -1 (assim como na Busca Linear!)
Mas muito cuidado! O tipo de retorno da função busca pode variar! Por exemplo, se a busca é feita num vetor de ponteiros para algo, se o elemento chave for encontrado, precisamos retornar um ponteiro né?
E se caso o elemento não for encontrado, >>Nesse Caso<< devemos retornar NULL ao invés de -1! (NULL representa um ponteiro vazio!) 
OBS: Essa é a base de >>TODA<< busca binária! Só muda um detalhezinho ou outro! Como por exemplo, o que a busca vai retornar se achar a chave (O índice do vetor ou o valor em si) e o critério de comparação.
-----------------------------------//--------------------------------------------
Exemplo 2: Temos um vetor de ponteiros para struct Aluno e a partir de uma turma e matrícula, queremos buscar a nota desse aluno: 
OBS: o vetor já está em ordem crescente por turma e para uma mesma turma está ordenado de forma crescente por matrícula!
typdef struct aluno{
 char turma[4];
 int matricula;
 float nota;
}Aluno;
int compara (Aluno *a, char *turma, int mat){
	int res;
	res = strcmp(turma, a->turma);
	if(res != 0) return res;
	else if(mat == a->matricula) return 0;
	else if(mat < a->matricula) return -1;
	return 1;
}
*********************************************************************************
OBS: A partir daqui >TODA< comparação da busca será sempre feita através de uma função auxiliar!!! As questões de prova já são organizadas dessa forma! (Letra A pede só a função de comparação, letra B pede a função busca, etc)
res = strcmp(turma, a->turma);
res = strcmp (O que buscamos, o que temos);
OBS: Recomendo sempre colocar os parâmetros da strcmp nessa ordem! Se inverter os parâmetros, inverte o resultado também! Cuidado! Lembrando que a função strcmp retorna um valor menor que zero (Se o nome que buscamos vem ANTES!), maior que zero (Se o nome que buscamos vem DEPOIS!) ou igual a zero se for igual!
Mas como são dois critérios, se caso a strcmp retornar zero (Achou a Turma!), mas não podemos retornar zero, pois ainda falta testar o segundo critério! (Matrícula)
Regra Importante: A comparação é feita de acordo com o critério de ordenação descrito no enunciado! >>TODA<< função auxiliar de comparação retorna um inteiro que pode ser um número menor que zero (Pra indicar pra busca que o que procuramos vem ANTES!), maior que zero (O que procuramos vem DEPOIS) ou igual a zero. (Achou!) 
*********************************************************************************
float busca (Aluno ** alunos, int n, char *turma, int mat){
	int ini, fim, meio, res;
	ini = 0;
	fim = n -1;
	while(ini <= fim){
		meio = (ini + fim)/2;
		res = compara (alunos[meio], turma, mat);
		if(res == 0) return alunos[meio]->nota;
		else if(res < 0) fim = meio - 1;
		else ini = meio + 1;
	}
	return -1;
}
OBS: Notou que é quase idêntica a busca binária que vimos no exemplo 1? :)
Levando em conta que esse Exemplo 2 é bem parecido com o que é cobrado em prova!
Como se trata de um vetor de ponteiros para Aluno, cada posição do vetor contém um ponteiro para Aluno. E como fazemos pra acessar a variável de algum ponteiro para estrutura?
alunos[meio]->nota; 
Usamos a setinha pra acessar qualquer variável dessa struct! 
OBS: E se o enunciado pedisse pra retornar o ponteiro para esse Aluno caso achar?
Só alterar três mini detalhes! O tipo de retorno da função de float passa a ser Aluno * (Ponteiro para Aluno)
Se caso achar: return alunos[meio]; 
Se não achar: return NULL;
OBS: Dúvidas quanto a Vetor de ponteiros e setinhas? É só dar uma lida no bloco "Resumo_Struct" e "Resumo_VetorDePonteiro"! :D
--------------------------------------//-----------------------------------------