{joseana, rangel}@dsc.ufcg.edu.br
DSC/CCT/UFCG
Prof.: José Eustáquio Rangel de Queiroz
[email protected]
[email protected]
Carga Horária: 60 horas
Busca em C I
DSC/CCT/UFCG

Considerações Iniciais I
 Suposição  Necessidade de localização/
recuperação de um número de telefone de
interesse em uma agenda implementada
computacionalmente
{joseana, rangel}@dsc.ufcg.edu.br
 Estratégia  Escrutínio do array desde o
seu início e verificação de todos os
nomes até a localização daquele
associado ao número de interesse ou até
que se atinja o final do array
2
Busca em C II
DSC/CCT/UFCG

Considerações Iniciais II
 Localização de informações em arrays
desordenados  Processo seqüencial,
do primeiro item ao item de interesse ou o
último item do array
{joseana, rangel}@dsc.ufcg.edu.br
 Localização de informações em arrays
ordenados  Processo de busca
binária, com fins à aceleração da tarefa
de recuperação do item de interesse
3
Busca em C III
DSC/CCT/UFCG

Busca Seqüencial I
 Codificação relativamente fácil
{joseana, rangel}@dsc.ufcg.edu.br
 Escolhas

Permissão de chaves não únicas?

Retorno do primeiro item de interesse
localizado ou de todos os itens
compatíveis com a busca?
 Número médio de tentativas

Chave única  ½ n

Chave não única  n
4
Busca em C IV
DSC/CCT/UFCG

Busca Seqüencial II
 Número de tentativas
Melhor caso  1
 Pior caso
n

 Força Bruta  Tempo de Execução é
{joseana, rangel}@dsc.ufcg.edu.br
O(n)
5
Busca em C V
DSC/CCT/UFCG

Busca Seqüencial III
{joseana, rangel}@dsc.ufcg.edu.br
 Algoritmo 01
int BuscaSeq(int l, int r, int x)
{
for (int i = l; i <= r; i++)
if (a[i] == x) return i;
return -1;
}
6
Busca em C VI
DSC/CCT/UFCG

Busca Binária I
 Base  Divisão para conquista
{joseana, rangel}@dsc.ufcg.edu.br


Verificação do item central do array

Se o item for maior do que a chave de
busca, execução do teste do item
central da primeira metade do array

Caso contrário, execução do teste do
item central da segunda metade do
array
Repetição do processo até a localização
do item ou a inexistência de itens de
teste
7
Busca em C VII
DSC/CCT/UFCG

Busca Binária II
 Número de tentativas

Busca insatisfatória  logn + 1
{joseana, rangel}@dsc.ufcg.edu.br
 Busca satisfatória
 Pior caso
 logn
 Caso Médio
 logn -1
 Melhor caso  1
 Tempo de Execução  O(logn)
8
Busca em C VIII
DSC/CCT/UFCG

Busca Binária III
{joseana, rangel}@dsc.ufcg.edu.br
 Algoritmo 02
int BuscaBin(int esq, int dir, int ch){
int meio;
if (esq > dir) return -1
else {
meio = (esq + dir)/2;
if (a[meio] == ch) return meio;
if (a[meio] > ch) return BuscaBin(esq,meio-1,ch);
else return BuscaBin(meio+1,dir,ch);
}
9
Busca em C IX
DSC/CCT/UFCG

Exercício 01
 Implementar
{joseana, rangel}@dsc.ufcg.edu.br
os algoritmos de busca
Seqüencial e Binária para arrays de
caracteres
10
Busca em C X
DSC/CCT/UFCG

Exercício 02
 Analisar o código apresentado nos slides
{joseana, rangel}@dsc.ufcg.edu.br
13 e 14, implementar a função Le_gente
em
um
arquivo
e
explicar
o
funcionamento do programa
11
Busca em C XI
DSC/CCT/UFCG

Exercício 02 (1/2)
{joseana, rangel}@dsc.ufcg.edu.br
#define TAM 30
#define MAX 100
typedef struct {
char prim[TAM];
char ult[TAM];
int alt;
int p;
} indiv;
indiv gente[MAX];
main(){
int i ;
Le_gente();
qsort(gente, n, sizeof(gente), Compara_gente);
for (i=0; i<n; i++)
printf(’’%s, %s\n’’, gente[i].ult, gente[i].prim);
}
12
Busca em C XII
DSC/CCT/UFCG
{joseana, rangel}@dsc.ufcg.edu.br

Exercício 02 (2/2)
int Compara_gente(indiv *a, indiv *b)
{
int res;
if (a->alt < b->alt) return (-1);
if (a->alt > b->p) return (1);
if (a->p < b->p) return (-1);
if (a->p > b->p) return (1);
if ((res=strcmp(a->ult, b->ult))!=0) return res;
return(strcmp(a->prim, b->prim));
}
13
DSC/CCT/UFCG
José Eustáquio Rangel de Queiroz
[email protected], [email protected]
{joseana, rangel}@dsc.ufcg.edu.br
UNIVERSIDADE FEDERAL DE CAMPINA GRANDE
CENTRO DE CIÊNCIAS E TECNOLOGIA
DEPARTAMENTO DE SISTEMAS E
COMPUTAÇÃO