[INF1007] Resumo Busca Binária

Prévia do material em texto

Programação II 
Monitor: André Vicente Pessanha 
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 "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 e/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 
 
 
­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­ // ­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­