Aula 02 - Algoritmos de Busca

Prévia do material em texto

[1]
Prof. Rogério Colpani
[2]Estrutura de Dados
1. Introdução
2. Algoritmo: Pesquisa sequencial
3. Algoritmo: Pesquisa binária
4. Exercícios
[3]Estrutura de Dados
Dada uma coleção de n elementos, pretende-se saber se um
determinado elemento (valor) está presente nessa coleção.
Livros na biblioteca Nome de pessoa
SalárioRGAltura
[4]Estrutura de Dados
Qual a criança mais 
alta?
[5]Estrutura de Dados
ACHOU !!!
[6]Estrutura de Dados
É a forma mais simples de busca.
Conhecido também por busca linear.
É aplicável a uma tabela organizada com um vetor ou como uma lista encadeada.
Percorre-se registro por registro em busca da chave.
[7]Estrutura de Dados
12 25 33 37 48 57 86 92
0 1 2 3 4 5 6 7
Encontrar o número 48
[8]Estrutura de Dados
12 25 33 37 48 57 86 92
0 1 2 3 4 5 6 7
12 é igual 48 ?
[9]Estrutura de Dados
12 25 33 37 48 57 86 92
0 1 2 3 4 5 6 7
25 é igual 48 ?
[10]Estrutura de Dados
12 25 33 37 48 57 86 92
0 1 2 3 4 5 6 7
33 é igual 48 ?
[11]Estrutura de Dados
12 25 33 37 48 57 86 92
0 1 2 3 4 5 6 7
37 é igual 48 ?
[12]Estrutura de Dados
12 25 33 37 48 57 86 92
0 1 2 3 4 5 6 7
ACHOU !!!
[13]Estrutura de Dados
template <class T>
int bSequencial ( T A[ ], T x, int n )
{
for ( int i = 0; i < n; i ++ )
{
if ( A [ i ] == x )
return i; // chave encontrada – retorna posição
}
return -1; // chave não encontrada
}
Ideia básica
Percorrer o vetor A desde a primeira posição até
a última. Para cada posição i, comparamos A[i]
com o valor ( x ).
• Se forem iguais: retorna a posição.
• Se chegarmos ao fim do vetor sem sucesso
retornamos -1, dizendo que o valor não
existe.
A implementação não suporta mais de um registro com uma mesma chave, pois retorna o primeiro encontrado.
[14]Estrutura de Dados
Registros devem estar ordenados.
 Para saber se uma chave está presente na tabela
1. Compare a chave com o registro que está na posição do meio da tabela.
2. Se a chave é menor então o registro procurado está na primeira metade 
da tabela.
3. Se a chave é maior então o registro procurado está na segunda metade 
da tabela.
4. Repita até que a chave seja encontrada ou que se constate que a chave 
não existe na tabela.
[15]Estrutura de Dados
template <class T>
int bBinaria ( T vetor [ ], T key, int n )
{
int imax = n – 1;
int imin = 0;
while ( imax >= imin )
{
int imid = imin + ( ( imax – imin ) / 2 ); // meio do vetor
if ( key > vetor [ imid ] )
imin = imid + 1;
else
if ( key < vetor [ imid ] )
imax = imid – 1;
else
return imid;
}
return -1;
}
[16]Estrutura de Dados
12 25 33 37 48 57 86
0 1 2 3 4 5 6
Encontrar o número 86
[17]Estrutura de Dados
12 25 33 37 48 57 86
0 1 2 3 4 5 6
n = 7 // tamanho do vetor
imax = n – 1 // 6
imin = 0 imaximin
[18]Estrutura de Dados
12 25 33 37 48 57 86
0 1 2 3 4 5 6
imid
imid = imin + ( ( imax – imin ) / 2 )
// = 0 + ( 6 – 0 ) / 2
// = 3 imaximin
[19]Estrutura de Dados
12 25 33 37 48 57 86
0 1 2 3 4 5 6
imid
if ( key > vetor [imid] ) // 86 > 37 ???
imin = imid + 1 // 3 + 1 = 4
imaximin
12 25 33 37 48 57 86
0 1 2 3 4 5 6
imaximin
[20]Estrutura de Dados
imid = imin + ( ( imax – imin ) / 2 )
// = 4 + ( 6 – 4 ) / 2
// = 5 
12 25 33 37 48 57 86
0 1 2 3 4 5 6
imid imaximin
[21]Estrutura de Dados
12 25 33 37 48 57 86
0 1 2 3 4 5 6
imid
if ( key > vetor [imid] ) // 86 > 57 ???
imin = imid + 1 // 5 + 1 = 6
imaximin
12 25 33 37 48 57 86
0 1 2 3 4 5 6
imin = imax
[22]Estrutura de Dados
imid = imin + ( ( imax – imin ) / 2 )
// = 6 + ( 6 – 6 ) / 2
// = 6
if ( key > vetor [ imid ] ) // 86 > 86 ???
If ( key < vetor [ imid ] ) // 86 < 86 ???
else
return imid; // 6
12 25 33 37 48 57 86
0 1 2 3 4 5 6
imid
imin = imax
[23]Estrutura de Dados
 Para um vetor de 7 inteiros V = 6, 9, 1, 13, 8, 2, 15, qual será o número máximo de
comparações se o elemento procurado for 1? E se o elemento procurado for 12?
(Utilize a busca sequencial).
 Para um vetor de 5 inteiros V = 1, 4, 6, 10, 14, qual será o número máximo de
comparações se o elemento procurado for 4? E se o elemento procurado for 14?
(Utilize a busca binária).
 Demonstre as etapas percorridas pela pesquisa sequencial para encontrar a posição
do item cuja a chave é 20.
5 15 6 7 10 1 8 20 3 4
0 1 2 3 4 5 6 7 8 9
[24]Estrutura de Dados
 Demonstre as etapas percorridas pela pesquisa sequencial para encontrar a posição
do item cuja a chave é 33.
 Depois de ordenar a sequência dos dados no vetor, demonstre as etapas percorridas
pela pesquisa binária para encontrar a posição do item cuja chave é Jorge.
5 15 21 22 26 32 33 33 34 40
0 1 2 3 4 5 6 7 8 9
Jair Valdir Carlos Jorge Bia Ana Zélia Manoel Carla
0 1 2 3 4 5 6 7 8
[25]Estrutura de Dados
 Crie um algoritmo que permita realizar o cadastro de 5 pessoas com os seguintes
dados: CPF, nome, endereço e idade. Logo depois de realizar o cadastro, o algoritmo
deve permitir ao usuário realizar uma pesquisa como exemplificado abaixo.
 O usuário deve informar o CPF da pessoa que deseja localizar e o algoritmo deve
utilizar o método de pesquisa sequencial para realizar a busca. Exibir na tela os
dados caso encontrado ou uma mensagem de “CPF não encontrado”.