Os Sistemas de Informação

CLASSIFICAÇÃO E PESQUISA

Pesquisa de Dados

Primeiramente serão apresentados dois métodos de pesquisa para então ser apresentados os métodos de ordenação. Os métodos de pesquisa apresentados são:

• Pesquisa seqüencial ou linear;
• Pesquisa binária.

Pesquisa de Dados: Seqüencial

A pesquisa seqüencial (ou busca linear) constitui a forma mais simples de busca de um elemento num conjunto de dados. Esta busca inicia no primeiro registro e segue seqüencialmente até encontrar o elemento (ou “chave”) procurado. Na pior situação possível, a busca passa por todos os elementos do conjunto e não o encontra, sendo que na melhor situação o elemento procurado está na primeira posição pesquisada. Este tipo de técnica é indicado para conjuntos ordenados ou não.

A seguir será ilustrada uma função de pesquisa seqüencial (negrito) em um programa em C:

#include

#include //função rand()

#define TAM 100

int p_sequencial(int vet[TAM], int N){

int i=0;

while ((N != vet[i]) && (i

        i++;

return (i);//retorna a posição do vetor em que o elemento está ou TAM se o elemento não estiver no vetor

}

void main(){

int vetor[TAM], i, pos,N;

for(i=0;i

        vetor[i]=rand();//gera números aleatórios

printf("Digite o valor a ser procurado no vetor:");

scanf("%d",&N);

pos=p_sequencial(vetor, N);

if(pos

        printf("O numero esta na posicao: %d", pos);

else

        printf("Numero nao existe no conjunto.");

}

Análise de Complexidade

1. No melhor caso, o registro com chave igual à procurada é encontrado na primeira posição, com apenas uma comparação.

C(n) = 1

1. No pior caso, de pesquisa bem sucedida, o registro é localizado na posição N, com um custo de N comparações.

C(n) = n

1. No caso médio, o número de comparações para localizar o registro é a média entre o pior e o melhor caso, ou seja, (N+1)/2. Portanto, a complexidade da pesquisa seqüencial é C(n), ou seja, cresce linearmente com o tamanho do vetor.

C(n) = (n +1)/2

1. Para pesquisas sem sucesso, temos o pior caso + 1.

C(n) = n +1.

Exemplo: Dado o vetor abaixo com 10 posições ou seja n = 10.

9

8

0

2

5

4

3

7

1

6

a) Quantas comparações são feitas para achar o número 9?  C(10) = 1

b) Quantas comparações são feitas para achar o número 5?  C(10) = 5

c) Quantas comparações são feitas para achar o número 6?  C(10) = 10

d) Quantas comparações são feitas para achar o número 10?  C(10) = 11

Exercício

1. Execute o programa de busca seqüencial mostrando o pior caso, o caso médio, melhor caso e o um caso sem sucesso, utilizando seu RA.
2. Dado o vetor A={9,7,5,2,4,6,10,3,1,8}  faça um algoritmo utilizando uma pesquisa seqüencial para encontrar os números pares.

Pesquisa de Dados: Binária

        

O algoritmo de busca binária só pode ser usado em um conjunto de dados ordenados. O processo consiste em "dividir para conquistar", logo:

• Divida um conjunto de elementos em duas partes;
• Compare com a chave do elemento do meio;
• Se a chave for igual ao elemento do meio, sucesso na busca (pare), se a chave comparada for menor, o elemento está na parte esquerda da lista, se maior, na parte direita;
• Aplique o método recursivamente.

Exemplo:

1. Verificar através da pesquisa binária se a chave “NEI” se encontra no vetor de registros ordenados segundo as chaves [ANA, BIA, CID, EVA, GIL, IVO, LIA, RUI]

Solução:

1	2	3	4	5	6	7	8
ANA	BIA	CID	EVA	GIL	IVO	LIA	RUI	Meio = (Esq+Dir)/2
↑			↑				↑	Meio = (1+8)/2 = 4
Esq			Meio				Dir

Como NEI > EVA, Esq = Meio + 1 = 4 + 1 = 5

				5	6	7	8
				GIL	IVO	LIA	RUI	Meio = (5+8)/2 = 6
				↑	↑		↑
				Esq	Meio		Dir

Como NEI > IVO, Esq = Meio + 1 = 6 + 1 = 7

						7	8
						LIA	RUI	Meio = (8+7)/2 =7
						↑	↑
						Esq, Meio	Dir

Como NEI > LIA, Esq = Meio + 1 = 7 + 1 = 8

							8
							RUI	Meio = (8+8)/2 =8
							↑
							Esq, Dir

Como NEI < RUI, Dir  = Meio - 1 = 8 - 1 = 7

 

A nova partição (Meio = 8 e Dir = 7) é uma partição vazia porque  meio>dir e, como não restam mais chaves, a pesquisa termina sem sucesso, ou seja, a chave NEI não foi localizada.

2. Verificar através da pesquisa binária se a chave “BIA” se encontra no vetor de registros ordenados segundo as chaves [ANA, BIA, CID, EVA, GIL, IVO, LIA, RUI]