kkkk

UNIDADE TIETÊ

Algoritmos e Estrutura de Dados Avançado
Prof. Luciano Soler

AED – Algoritmos e Estrutura de Dados

Métodos de Pesquisa
• Banco de dados existem para que, de tempos em tempos, se possa acessar um determinado registro, simplesmente digitando uma chave de busca.
• Existem apenas dois métodos de pesquisa:
1. Um para localização em arquivos desordenados
2. Um para localização em arquivos ordenados

• Para efeitos de simplificação, vamos supor que:
– Os métodos de pesquisa serão implementados sobre um vetor de N elementos; – Pretende-se saber se um determinado elemento está presente no vetor. AED – Algoritmos e Estrutura de Dados

Métodos de Pesquisa
Pesquisa Sequencial
• Encontrar informações em arquivos DESORDENADOS
• Percorre todo o vetor desde a primeira posição até a última.
• Obs.: também pode ser utilizado na busca em arquivos ordenados, embora não seja aconselhável.
• Algoritmo:
1.
2.
3.

Para cada posição i, comparar v[i] com o valor;
Se forem iguais, dizemos que o valor existe;
Se chegarmos ao fim do vetor sem sucesso, dizemos que o valor não existe. AED – Algoritmos e Estrutura de Dados

Métodos de Pesquisa
Análise da Pesquisa Sequencial
• Quanto tempo este algoritmo demora para executar ?
• Quantas vezes é realizada a comparação v[i]==x ?
1. Caso o valor não esteja no vetor: N vezes
2. Caso o valor esteja no vetor:
•

Melhor caso: UMA vez (valor na 1º. posição)

•

Pior caso: N vezes (valor na última posição)

•

Caso Médio: N/2 vezes

AED – Algoritmos e Estrutura de Dados

Métodos de Pesquisa
Pesquisa Binária
• Encontrar informações em arquivos ORDENADOS
• Resolve o problema da pesquisa de modo mais eficiente
• Utiliza a abordagem “dividir para conquistar”
• Com os dados ordenados podemos saber:
1. Se o elemento procurado está antes do comparado
2. Se o elemento procurado está depois do comparao

AED – Algoritmos e Estrutura de Dados

Métodos de Pesquisa
Pesquisa