Prática05-PesquisaSequencial_e_Binaria

Prévia do material em texto

Algoritmos e Técnicas de 
Programação
Prática 05 – Implementação dos Algoritmos 
de Pesquisa Sequencial e Binária
Objetivos: Implementar a Pesquisa (Busca) 
Sequencial e Binária:
� Incorporar ao Programa da Prática Passada 
(Aplicação de Vetores):
� Pesquisa Sequencial
� Pesquisa Binária (vetor ordenado)
� Como atividade complementar, os dois 
algoritmos deverão ser modificados para 
computar o número de comparações 
necessárias para localizar, ou não, um 
elemento.
Adicionar as opções 6 e 7 ao Programa
Pesquisa Seqüencial
//“v”: vetor; “e”, “d”: extremos esquerdo (0) e direito (n-1)
//“x”: valor procurado
//“pos”: posição do elemento, se encontrado
//retorno: (1 = encontrado, 0 = não encontrado) 
int PesquisaSeq(int v[], int e, int d, int x, int * pos)
{
int i = e;
while (i <= d && x != v[i])
i++;
if (i <= d)
{ //elemento encontrado
*pos = i;
return 1;
}
else
return 0;
}
Pesquisa Sequencial – Interação/Usuário
� Antes da Chamada
� Depois, com sucesso
� Depois, sem sucesso
Pesquisa Binária: PseudoCódigo
// V: Vetor ordenado
// e: limite esq. (inferior)
// d: limire dir. (superior)
// x: valor procurado
// pos: posição da 1a ocorr.
// retorno: verd = encontrado!
função PesquisaBin (V : Vetor; 
e, d : inteiro;
x : inteiro; 
PorRef Pos: inteiro): lógico
declare 
m : inteiro
Res : lógico
início
Res ← Falso
enquanto e ≤ d faça
m ← (e + d) div 2
se x > V[m] então
e ← m + 1
senão
d ← m - 1
se x = V[m] então
Res ← Verdadeiro
fim_se
fim_se
fim_enquanto
Pos ← e
retorne Res
fim
Busca Binária: Fragmentos em C
� Protótipo:
int PesquisaBin(int v[], int e, int d,
int x, int * pos)
� Declarações adicionais em “main()”:
� Variáveis:
int x, pos; //valor procurado e posição
� Texto de interação com o usuário (próximo slide)
� Chamada da função PesquisaBin
if (PesquisaBin(v, 0, n-1, x, &pos))
//o valor x foi encontrado na posição pos
Printf("...", ...);
else
//o valor x não foi encontrado, mas sua posição seria pos
Printf("...", ...);
Pesquisa Binária – Interação/Usuário
� Antes da Chamada
� Depois, com sucesso
� Depois, sem sucesso
Exercício Recomendado
� Implemente um função que utilize um dos 
algoritmos de pesquisa vistos para listar as 
posições de todas as ocorrências de um 
determinado elemento (valor).
� SUGESTÃO: na primeira pesquisa, use e = 0; se o 
elemento for encontrado em pos, proceda à segunda 
pesquisa a partir de e = pos + 1, e assim por diante, até
que o algoritmo não encontre qualquer elemento entre e e 
d (extremos esquerdo e direito do vetor). 
� NOTA: este exemplo ilustra bem como e e d (passados 
como parâmetro par a função) tornam a pesquisa mais 
flexível, ou seja, permitem restringir a faixa de procura.