Métodos de Pesquisa - Programação

Pesquisa / Busca

[e-mail]
1

Algoritmos de Busca
- Busca Linear
- Busca por Interpolação

- Busca Binária

2

Busca Linear
- Único método possível de ser utilizado em dados desordenados; - É baseado em uma heurística “passe ao próximo”;
- Pouca inteligência, muito esforço

- Tempo de execução:
- Se o elemento procurado for o primeiro: 1
- Se o elemento procurado for o último: n
- Média = n/2
3

Busca Linear
- Buscar o valor 4 no seguinte vetor:
2 1 5 4 3 9 7
2 1 5 4 3 9 7

2 1 5 4 3 9 7 ic ic

2 1 5 4 3 9 7

2 1 5 4 3 9 7

ic

ic

Achou ? Para, e retorna ic
Exemplo:
http://www.cosc.canterbury.ac.nz/people/mukundan/dsal/LSearch.html4

Busca por Interpolação
- Método que necessita da informação ordenada;
- Princípio semelhante a busca de um nome em uma lista telefônica, por exemplo;
- Se baseia na seguinte fórmula:

- Tempo de execução:
- Pior caso: n
- Média = log(log(n))

( j  i) * ( x  ai ) mi (a j  ai )

5

Busca por Interpolação
- Buscar o valor 4 no seguinte vetor:

( j  i) * ( x  ai ) mi (a j  ai )

1 2 4 6 8 9 12 i=1 j=7

i=3 j=7 1 2 4 6 8 9 12

1 2 4 6 8 9 12

m

se X > Am se X < Am se X = Am

m

i = m+1 j=m retorna

6

Busca Binária
- Informação ordenada;
- Dividir para Conquistar;

- Divide os dados sempre na metade:
- Se valor < “valor no meio” busca do início até o meio
- Se valor > “valor no meio” busca do meio até o fim
- Senão encontrou o valor
- Tempo de execução:
- Pior caso: log2(n)
7

Busca Binária
- Buscar o valor 4 no seguinte vetor:
1 2 4 6 8 9 12
1 2 4 6 8 9 12 i 1 2 4 6 8 9 12 i 1 2 4 6 8 9 12 i Exemplo: http://www.cosc.canterbury.ac.nz/people/mukundan/dsal/BSearch.html 8

Considerações Finais
Busca Linear  Único para dados desordenados;
Tempo médio e pior caso muito alto.
Busca por Interpolação  mais rápido no MC; fórmula complexa; pior caso muito ruim.
Busca Binária 