CST EM ANÁLISE E DESENVOLVIMENTO DE SISTEMA
Linguagem C
Linguagem de Programação X
Métodos de Pesquisa
Joseane Alves Freire
2ª Semestre 2009
Introdução
• Apresentaremos e discutiremos diferentes
estratégias para efetuarmos a pesquisa (busca)
de um elemento específico em um conjunto de
dados.
• Esta operação é muito importante, pois é
encontrada com muita freqüência em diversas
aplicações.
• Apresentaremos os métodos de pesquisa
seqüencial e binária sobre a estrutura de dados
vetor.
Pesquisa Seqüencial
• Pesquisa Seqüencial (PS)
– Metodologia: É efetuada a verificação de cada elemento do
conjunto, seqüencialmente, até que o elemento desejado seja
encontrado (pesquisa bemsucedida), ou que todos os elementos
do conjunto tenham sido verificados sem que o elemento
procurado tenha sido encontrado(pesquisa mal-sucedida).
– Utilizado quando os elementos da variável indexada não estão
ordenados.
1
2
14 21
3
5
4
5
45 12
6
3
7
8
9
10
11
12
13
86 98 46 53 24
2
1
14
15
16
15 90 47
– Como encontrar o elemento ’12’ no vetor?
– Quantas comparações foram necessárias neste caso?
Pesquisa Seqüencial
• Características
– Forma mais simples de realizar pesquisas.
– Pode ser muito ineficiente quando o conjunto de dados é muito
grande.
• Desempenho
– Pior Caso: é quando é necessário realizar n comparações (onde
n é o número de elementos);
• Qual o cenário de pior caso possível ?
– Melhor Caso: é quando é necessário realizar somente uma
comparação;
• Qual o cenário de pior caso possível ?
– Caso Médio: é quando é necessário realizar cerca de n/2
comparações.
• Qual o cenário de pior caso possível ?
Pesquisa Seqüencial
• Código
/*Faz a pesquisa sequencial do elemento val no vetor a[]*/
int pesquisa_sequencial(int a[], int n, int val){
int i;
for(i=0;i<n;i++)
if(a[i]==val) return 1;
return 0;
}
– Dá pra fazer melhor????
Pesquisa Binária
• É utilizado quando os elementos da variável indexada
estão previamente ordenados e funciona assim:
– O elemento que se encontra no meio (aproximado) do vetor é
localizado e comparado ao valor procurado.
– Se ele for igual ao valor procurado, a pesquisa é bem sucedida e
terminada.
– Se ele for maior que o valor procurado, repete-se o processo na
primeira metade do vetor.
– Se ele for menor que o valor procurado, repete-se o processo na
segunda metade do vetor.
– Este processo é continuado até que o valor procurado seja
localizado (pesquisa bem sucedida).
– ou então até que não reste mais um trecho do vetor a ser
pesquisado (pesquisa mal-sucedida).
Pesquisa Binária
• Desempenho
– Pior Caso:
• Elemento não ocorre no vetor.
• Duas comparações são realizadas a cada ciclo.
• A cada repetição, a parte considerada na busca é
dividida à metade
• Complexidade log2 n.
Ilustração da Pesquisa Binária
Fluxograma da
Busca Binária
Busca Binária
• Código
/*Faz a pesquisa binária do elemento val no vetor a[]*/
int pesquisa_binaria(int a[], int n, int val){
int inicio=0, meio, fim=n-1, achou=0;
while ((achou!=1) && (inicio <= fim)){
meio = (inicio+fim)/2;
if(val == a[meio])
achou=1;
else{
if (val < a[meio])
//vamos procurar na primeira metade do
vetor
fim = meio - 1;
//para isso basta mudar o indice FIM.
else
//vamos procurar na segunda metade do
vetor
inicio = meio + 1; //para isso basta mudar o indice INICIO.
}
}
return achou;
}
Comparando a Busca Seqüencial e
Binária
• Busca Seqüencial O(n)
• Busca Binária O (log2 n)
• Exemplo: considere uma lista de 10.000
elementos
– A busca binária realizaria no pior caso 14
comparações enquanto que a busca seqüencial
realizaria em média 5.000 comparações
Exercício
• Considere o vetor com 11 elementos
abaixo e diga quantas comparações de
igualdade realizam os algoritmos de
Busca Linear e Busca Binária, na
tentativa de se encontrar no vetor os
valores:
a) 3
b) 25
c) 70