Ordenacao 1x2

6. Pesquisa e Ordenação
Fernando Silva
DCC-FCUP

Estruturas de Dados

Fernando Silva (DCC-FCUP)

6. Pesquisa e Ordenação

Estruturas de Dados

1 / 30

Pesquisa de Informação
A pesquisa eficiente de informação é extremamente relevante, seja: pesquisa num catálogo indexado por uma relação de ordem, e.g. alfabética, como seja uma lista telefónica; pesquisa interna nos registos de uma base de dados: registos ordenados ou não ordenados; pesquisa de informação em páginas Web (pesquisa de texto); pesquisa de informação em dados binários, normalmente imagens, etc.
A pesquisa sequencial é dos casos mais simples e é normalmente usada quando não se tem uma relação de ordem na informação a pesquisar.

Fernando Silva (DCC-FCUP)

6. Pesquisa e Ordenação

Estruturas de Dados

2 / 30

Pesquisa Sequencial
A pesquisa sequencial consiste em procurar um valor x numa sequência de valores v [] com dimensão N.
Vejamos a pesquisa com valores inteiros e strings (veremos mais tarde como fazer o mesmo com apenas um método):

Fernando Silva (DCC-FCUP)

6. Pesquisa e Ordenação

Estruturas de Dados

3 / 30

Pesquisa Binária
A pesquisa binária é uma estratégia eficiente de pesquisa de um valor x numa sequência ordenada de valores v [] indexado no intervalo (e, d):
Ideia do algoritmo:

Um exemplo:

Seja m a posição média de v[]
Comparar x com v[m]
Se x==v[m] então encontrou senão se x<v[m], procura x no intervalo [e,m-1] senão (x>v[m]), procura x no intervalo [m+1,d]

Fernando Silva (DCC-FCUP)

6. Pesquisa e Ordenação

Estruturas de Dados

4 / 30

Pesquisa Binária: versão recursiva

Fernando Silva (DCC-FCUP)

6. Pesquisa e Ordenação

Estruturas de Dados

5 / 30

Estruturas de Dados

6 / 30

Pesquisa Binária: versão não recursiva

Fernando Silva (DCC-FCUP)

6. Pesquisa e Ordenação

Pesquisa Indirecta
Seja int o[] um vector que determina a ordem dos elementos de uma sequência de nomes String nomes[]. Como pesquisar a string nome no vector nomes[]?
Efectuar pesquisa binária dos nomes através do