Algoritmos de Busca
Prof. Frederico Brito Fernandes
[email protected]
CONTEÚDO
(1) Motivação
(2) Busca Linear
(3) Busca Binária
(1) Motivação
Buscando informação...
• Imagine um vetor de elementos no qual os objetos foram
posicionados em determinada ordem.
– Dicionário ou um catálogo de telefones
– O arquivo da folha de pagamento de uma empresa
• Suponha que esse vetor exista e desejemos localizar
determinado elemento dentro dele.
– pesquisar um nome num catálogo de telefones, uma palavra num
dicionário ou determinado empregado num arquivo de pessoal.
• O processo usado para encontrar tal elemento é chamado
busca
– Queremos descobrir um método eficiente para executar a busca
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
2
(2) Busca Linear
Busca Linear
• O método de busca mais simples é o da busca seqüencial ou linear
– cada item do vetor é examinado por vez e comparado ao item que se está
procurando, até ocorrer uma coincidência.
O(n)
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
3
(2) Busca Linear
Busca Linear (lista ordenada)
• Se a lista não estiver ordenada, talvez seja a única maneira de
localizar algo dentro dela
• Entretanto, para localizar um item dentro de uma lista ordenada, há
um algoritmo de busca linear mais eficiente
O(n)
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
4
(2) Busca Linear
Busca Linear
• Por que o algoritmo anterior é mais eficiente do que o
primeiro?
• Podemos fazer um algoritmo de busca ainda mais
eficiente do que estes?
– Imagine um dicionário. Como você faria uma busca nele?
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
5
(3) Busca Binária
Busca Binária
• Compare o elemento sendo procurado ao elemento posicionado no
meio do vetor.
• Se forem iguais, a busca terminou com sucesso.
• Se o elemento do meio for maior que o elemento sendo procurado, o
processo de busca será repetido na primeira metade do vetor
• Caso contrário, o processo será repetido na segunda metade.
• Por causa da divisão pela metade da lista sendo pesquisada, esse
método de busca é chamado busca binária.
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
6
(3) Busca Binária
Busca Binária X Busca Linear
• Toda vez que uma comparação é feita, o número de
elementos a pesquisar é cortado pela metade.
– Para os vetores grandes e ordenados, esse método é mais eficiente do
que a busca linear.
O(log n)
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
7
Exercícios
• É possível implementar uma busca binária em uma lista ligada?
• Implemente programas que utilizem os algoritmos apresentados
nesta aula.
– Busca linear numa lista de pessoas em um cinema (chave de busca é o
CPF)
• Fazer versão com vetor e com lista encadeada
– Busca linear numa lista de alunos em um diário de classe eletrônico
(chave de busca é a matrícula)
• Fazer versão com vetor e com lista encadeada
– Busca binária em um vetor de alunos que represente um diário de
classe eletrônico
• Fazer versão iterativa e recursiva
Estrutura, Pesquisa e Ordenação de Dados
Frederico Brito Fernandes
8