ACFrOgAzIl 00UQaD5UDQhMksiXX vVfkrbbvVjrUk5DoTvSItjuclkfNIkXhtWFJDz77XQ7QcBL53WwYi4II0 wfXtXdeCS7eZx07zAgi7au4I69m 5sAcCQjMZagM=

Prévia do material em texto

CLASSIFICAÇÃO E 
PESQUISA
Prof. Odair Moreira de Souza
Unidade 02
Encontro 01
Recapitulando...
• Introdução a complexidade computacional.
• Algoritmos para ordenação:
◦ Ordenação por Permutação (Bubble Sort);
◦ Ordenação por Inserção (Insertion Sort);
◦ Ordenação por Seleção (Selection Sort);
◦ Ordenação por Intercalação (Merge Sort);
◦ Ordenação Rápida (Quick Sort); e,
• Ordenação Heap (HeapSort);
12-Sep-17 Classificação e Pesquisa de Dados - Prof. Odair Moreira de Souza 2
Conteúdo
• Pesquisa Sequencial
• Pesquisa Binária
12-Sep-17 Classificação e Pesquisa de Dados - Prof. Odair Moreira de Souza 3
O problema da Pesquisa
“Dado um conjunto de elementos, onde cada um é
identificado por uma chave, o objetivo da busca é
localizar, nesse conjunto, o elemento que corresponde a
uma chave específica.”
12-Sep-17 Classificação e Pesquisa de Dados - Prof. Odair Moreira de Souza 4
O problema da Pesquisa
• Importância da operação de pesquisa
• É uma tarefa muito comum
• Deve, portanto, ser realizada de maneira eficiente
• Certas formas de organização de dados podem tornar o processo 
de busca mais eficiente
12-Sep-17 Classificação e Pesquisa de Dados - Prof. Odair Moreira de Souza 5
Tipos de Busca
• O conjunto de dados pode ser:
• Um vetor
• Uma lista encadeada
• Uma árvore
• etc
• A tabela pode ficar:
• Totalmente na memória primária (busca interna)
• Totalmente na memória secundária (busca externa)
• Dividida entre ambos
• Nesta aula, veremos a busca interna em vetor
12-Sep-17 Classificação e Pesquisa de Dados - Prof. Odair Moreira de Souza 6
Tipos de Busca
•Algumas técnicas de busca interna:
•Busca Sequencial
•Busca Binária
•Hashing
•etc
•O objetivo é realizar a busca com o menor custo (maior eficiência)
•Cada técnica possui suas vantagens e desvantagens
12-Sep-17 Classificação e Pesquisa de Dados - Prof. Odair Moreira de Souza 7
Pesquisa Sequencial
Pesquisa Sequencial
•Busca sequencial: é a mais simples que existe!
•Percorre-se elemento por elemento sequencialmente
•Procure por 48
•V={12, 25,33,37,48,57,86,92}
•Demostração
12-Sep-17 Classificação e Pesquisa de Dados - Prof. Odair Moreira de Souza 9
Pesquisa Sequencial
•Implementação 01:
12-Sep-17 Classificação e Pesquisa de Dados - Prof. Odair Moreira de Souza 10
Pesquisa Sequencial
•Implementação 02:
12-Sep-17 Classificação e Pesquisa de Dados - Prof. Odair Moreira de Souza 11
Pesquisa Sequencial - Análise
•Considerando um vetor, em que não há posições vazias entre os elementos 
válidos, e os dados não obedecem a nenhuma ordenação, a única forma de 
pesquisa é a busca sequencial.
• Se o elemento procurado está no vetor, temos:
• Melhor caso: custo = 1 (encontra na primeira posição)
• Pior caso: custo = N (encontra na última posição)
• Caso médio: custo = N/2
• Se o elemento não está no vetor:
• É necessário passar por TODOS os elementos, para verificar que o elemento não existe
• custo = N.
12-Sep-17 Classificação e Pesquisa de Dados - Prof. Odair Moreira de Souza 12
Custo: O(n)
Pesquisa Binária
Pesquisa Binária
•Algoritmo:
• O elemento buscado é comparado ao elemento do meio do vetor
• Se iguais, a busca é bem sucedida
• Se menor, continua a busca na metade inferior do vetor
• Se maior, continua a busca na metade superior do vetor
12-Sep-17 Classificação e Pesquisa de Dados - Prof. Odair Moreira de Souza 14
Pesquisa Binária
•Busca 25
•V = {12,25,33,37,48,57,86,92}
•Demostração
12-Sep-17 Classificação e Pesquisa de Dados - Prof. Odair Moreira de Souza 15
Pesquisa Binária
•Implementação:
12-Sep-17 Classificação e Pesquisa de Dados - Prof. Odair Moreira de Souza 16
Pesquisa Binária
•Implementação:
12-Sep-17 Classificação e Pesquisa de Dados - Prof. Odair Moreira de Souza 17
Pesquisa Binária
•Análise:
•Cada comparação reduz o número de possíveis candidatos por um fator de 2.
•Exemplo:
•A cada iteração, descarta-se metade do conjunto a pesquisar. Se iniciarmos com 1000 
elementos, temos:
1000 -> 500 -> 250 -> 125 -> 63 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1
12-Sep-17 Classificação e Pesquisa de Dados - Prof. Odair Moreira de Souza 18
Custo: O(log 2 N)
Atividades
1. Escreva um algoritmo de busca sequencial para um vetor de 
elementos ordenados em ordem crescente, otimizando a detecção 
da não existência da chave de busca.
2. Escreva uma versão da busca sequencial para um vetor de 
elementos ordenados em ordem crescente, decidindo por uma 
busca a partir do início ou a partir do final do vetor (reversa) 
com base no valor da chave.
12-Sep-17 Classificação e Pesquisa de Dados - Prof. Odair Moreira de Souza 19
Atividades
3. Escreva uma versão recursiva da rotina de busca binária.
4. Escreva uma versão da busca binária para objetos que 
implementem a interface Comparable.
12-Sep-17 Classificação e Pesquisa de Dados - Prof. Odair Moreira de Souza 20
Atividades
5. O problema da busca por uma chave é geralmente diferente dos exemplos 
mostrados. Ao invés de retornar a posição do dados, a intenção é passar uma 
chave (por exemplo, um código), e retornar o dado (objeto) correspondente 
ao código. Se nenhum objeto com a chave informada for encontrado, é 
retornado um valor nulo. Escreva um classe Produto, com código, descrição, 
saldo de estoque, valor de compra, etc... A seguir, escreva uma versão da 
busca binária que busque um Produto num vetor, com base num código 
informado:
Produto buscaBinaria(int codigo, Produto vet[]) { ... }
12-Sep-17 Classificação e Pesquisa de Dados - Prof. Odair Moreira de Souza 21
Resumo da Aula
12-Sep-17 Classificação e Pesquisa de Dados - Prof. Odair Moreira de Souza 22
Pesquisa Sequencial
Pesquisa Binária
Próxima Aula
12-Sep-17 Classificação e Pesquisa de Dados - Prof. Odair Moreira de Souza 23
Tabela hash