09.Busca - Aula sobre algoritmos de busca

Prévia do material em texto

Aula 08
Algoritmos de Pesquisa
Rodolfo Carneiro Cavalcante
Universidade Federal de Alagoas – UFAL
Campus Arapiraca
26 de Novembro de 2015
Rodolfo Carneiro Cavalcante (UFAL) Aula 08Algoritmos de Pesquisa 26 de Novembro de 2015 1 / 24
Suma´rio
1 Introduc¸a˜o
2 Pesquisa Sequencial
3 Pesquisa Bina´ria
Rodolfo Carneiro Cavalcante (UFAL) Aula 08Algoritmos de Pesquisa 26 de Novembro de 2015 2 / 24
Introduc¸a˜o
Suma´rio
1 Introduc¸a˜o
2 Pesquisa Sequencial
3 Pesquisa Bina´ria
Rodolfo Carneiro Cavalcante (UFAL) Aula 08Algoritmos de Pesquisa 26 de Novembro de 2015 3 / 24
Introduc¸a˜o
Introduc¸a˜o
Estudo de como recuperar informac¸a˜o a partir de uma determinada
quantidade de informac¸a˜o previamente armazenada
A informac¸a˜o e´ dividida em registros
Cada registro possui uma chave para ser usada na pesquisa
Objeto e´ encontrar uma ou mais ocorreˆncias de registros com chaves
iguais a` chave de pesquisa
Qual me´todo de pesquisa utilizar: depende!
da quantidade de dados envolvidos
se o arquivo esta´ sujeito a inserc¸o˜es e retiradas frequentes
Rodolfo Carneiro Cavalcante (UFAL) Aula 08Algoritmos de Pesquisa 26 de Novembro de 2015 4 / 24
Introduc¸a˜o
Introduc¸a˜o
E´ importante considerar algoritmos de pesquisa como tipos abstratos
de dados
Podemos embutir as func¸o˜es de pesquisa dentro de alguma estrutura
de dados ja´ estudada
Operac¸o˜es comuns
inicializar estrutura
Inserir registro
Retirar registro
Ordenar o arquivo para obter registros em ordem de acordo com a
chave
Pesquisar um ou mais registros
...
Rodolfo Carneiro Cavalcante (UFAL) Aula 08Algoritmos de Pesquisa 26 de Novembro de 2015 5 / 24
Introduc¸a˜o
Introduc¸a˜o
Tipicamente chamamos uma TAD criada especificamente para
pesquisa de arquivos de diciona´rio
Principais operac¸o˜es do TAD diciona´rio:
Inicializar
Pesquisar
Inserir
Retirar
Rodolfo Carneiro Cavalcante (UFAL) Aula 08Algoritmos de Pesquisa 26 de Novembro de 2015 6 / 24
Pesquisa Sequencial
Suma´rio
1 Introduc¸a˜o
2 Pesquisa Sequencial
3 Pesquisa Bina´ria
Rodolfo Carneiro Cavalcante (UFAL) Aula 08Algoritmos de Pesquisa 26 de Novembro de 2015 7 / 24
Pesquisa Sequencial
Pesquisa Sequencial
Me´todo de pesquisa mais simples
Falamos do funcionamento desse tipo de pesquisa quando
trabalhamos TAD lista
Funcionamento:
a partir do primeiro registro, verifique os registros sequencialmente ate´
encontrar a chave procurada
ou ate´ verificar todos os registros
Retorna o ı´ndice do registro que conte´m a chave pesquisada
Rodolfo Carneiro Cavalcante (UFAL) Aula 08Algoritmos de Pesquisa 26 de Novembro de 2015 8 / 24
Pesquisa Sequencial
Pesquisa Sequencial
Algoritmo 1: Pesquisa sequencial
pesquisa(arquivo, tam, chave){
se(tam!=0){
para i de 0 ate tam{
se (arquivo[i] == chave)
retorne i;
}
}
retorne -1;
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 08Algoritmos de Pesquisa 26 de Novembro de 2015 9 / 24
Pesquisa Sequencial
Pesquisa Sequencial
Breve ana´lise do me´todo
Melhor caso: item procurado esta´ na primeira posic¸a˜o
nu´mero de comparac¸o˜es: 1
Pior caso: item procurado esta´ na u´ltima posic¸a˜o
nu´mero de comparac¸o˜es: n
Caso me´dio: item procurado esta´ na posic¸a˜o do meio
Segundo alguns autores, o algoritmo de pesquisa sequencial e´ a
melhor escolha para arquivos com ate´ 25 registros
Rodolfo Carneiro Cavalcante (UFAL) Aula 08Algoritmos de Pesquisa 26 de Novembro de 2015 10 / 24
Pesquisa Bina´ria
Suma´rio
1 Introduc¸a˜o
2 Pesquisa Sequencial
3 Pesquisa Bina´ria
Rodolfo Carneiro Cavalcante (UFAL) Aula 08Algoritmos de Pesquisa 26 de Novembro de 2015 11 / 24
Pesquisa Bina´ria
Pesquisa Bina´ria
Pesquisa pode ser mais eficiente se registros forem mantidos em
ordem
Como funciona a busca por palavras em um diciona´rio de um idioma
qualquer?
Rodolfo Carneiro Cavalcante (UFAL) Aula 08Algoritmos de Pesquisa 26 de Novembro de 2015 12 / 24
Pesquisa Bina´ria
Pesquisa Bina´ria
Algoritmo
1 Compare a chave com o registro que esta´ na posic¸a˜o do meio do
arquivo
2 Se a chave de busca e´ menor, enta˜o o registro procurado esta´ na
primeira metade do arquivo
3 Se a chave de busca e´ maior, enta˜o o registro procurado esta´ na
segunda metade do arquivo
4 Repita o processo ate´ encontrar o registro buscado ou restar apenas
um registro o que significa pesquisa sem sucesso
Rodolfo Carneiro Cavalcante (UFAL) Aula 08Algoritmos de Pesquisa 26 de Novembro de 2015 13 / 24
Pesquisa Bina´ria
Pesquisa Bina´ria
Exemplo
x = [1,3,4,7,8,11,16,17,18,19,20]
chave de busca = 3
Rodolfo Carneiro Cavalcante (UFAL) Aula 08Algoritmos de Pesquisa 26 de Novembro de 2015 14 / 24
Pesquisa Bina´ria
Pesquisa Bina´ria
Exemplo
x = [1,3,4,7,8,11,16,17,18,19,20]
chave de busca = 3
comparac¸a˜o: 3==11?
Rodolfo Carneiro Cavalcante (UFAL) Aula 08Algoritmos de Pesquisa 26 de Novembro de 2015 15 / 24
Pesquisa Bina´ria
Pesquisa Bina´ria
Exemplo
x = [1,3,4,7,8,11,16,17,18,19,20]
chave de busca = 3
comparac¸a˜o: 3==11?
Na˜o, mas e´ menor, logo procura na primeira metade
Rodolfo Carneiro Cavalcante (UFAL) Aula 08Algoritmos de Pesquisa 26 de Novembro de 2015 16 / 24
Pesquisa Bina´ria
Pesquisa Bina´ria
Exemplo
x = [1,3,4,7,8]
chave de busca = 3
comparac¸a˜o: 3==4?
Rodolfo Carneiro Cavalcante (UFAL) Aula 08Algoritmos de Pesquisa 26 de Novembro de 2015 17 / 24
Pesquisa Bina´ria
Pesquisa Bina´ria
Exemplo
x = [1,3,4,7,8]
chave de busca = 3
comparac¸a˜o: 3==4?
Na˜o, mas e´ menor, logo procura na primeira metade
Rodolfo Carneiro Cavalcante (UFAL) Aula 08Algoritmos de Pesquisa 26 de Novembro de 2015 18 / 24
Pesquisa Bina´ria
Pesquisa Bina´ria
Exemplo
x = [1,3]
chave de busca = 3
comparac¸a˜o: 3==1?
Rodolfo Carneiro Cavalcante (UFAL) Aula 08Algoritmos de Pesquisa 26 de Novembro de 2015 19 / 24
Pesquisa Bina´ria
Pesquisa Bina´ria
Exemplo
x = [1,3]
chave de busca = 3
comparac¸a˜o: 3==1?
Na˜o, mas e´ maior, logo procura na segunda metade
Rodolfo Carneiro Cavalcante (UFAL) Aula 08Algoritmos de Pesquisa 26 de Novembro de 2015 20 / 24
Pesquisa Bina´ria
Pesquisa Bina´ria
Exemplo
x = [3]
chave de busca = 3
comparac¸a˜o: 3==3?
Rodolfo Carneiro Cavalcante (UFAL) Aula 08Algoritmos de Pesquisa 26 de Novembro de 2015 21 / 24
Pesquisa Bina´ria
Pesquisa Bina´ria
Exemplo
x = [3]
chave de busca = 3
comparac¸a˜o: 3==3?
Sim, enta˜o retorne o registro
Rodolfo Carneiro Cavalcante (UFAL) Aula 08Algoritmos de Pesquisa 26 de Novembro de 2015 22 / 24
Pesquisa Bina´ria
Pesquisa Bina´ria
Algoritmo 2: Pesquisa Bina´ria
busca(chave, arquivo[], tam){
pos = -1;
se (tam==0) retorne pos;
senao{
ini = 0; fim = tam-1;
faca{
pos = (ini+fim)/2;
se(chave < arquivo[pos])
fim = pos - 1;
senao
ini = pos + 1;
}enquanto(chave!=arquivo[pos] e ini<=fim);
}
se(chave==arquivo[pos]) retorne pos;
senao retorne -1;
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 08Algoritmos de Pesquisa 26 de Novembro de 2015 23 / 24
Pesquisa Bina´ria
Du´vidas
Utilizem o grupo para tirar du´vidas!
Rodolfo Carneiro Cavalcante (UFAL) Aula 08Algoritmos de Pesquisa 26 de Novembro de 2015 24 / 24
	Introdução
	Pesquisa Sequencial
	Pesquisa Binária