ALGORITMOS DE PESQUISA - di.ubi.ptcbarrico/Disciplinas/ProgramacaoAlgoritmos/... · Algoritmos de Pesquisa Programação II. Pesquisa Binária – versão iterativa 15/34 Pesquisa

1/34

ALGORITMOS DE

PESQUISA

Algoritmos de Pesquisa Programação II

Pesquisa 2/34

Pesquisa

Definição

- A operação de pesquisa permite

- encontrar um dado elemento num dado conjunto, ou

- concluir que um dado elemento não existe num dado conjunto

- A pesquisa de um elemento pode ser feita

- num conjunto ordenado ou

- num conjunto não ordenado.

- Quando o conjunto não está ordenado,

- o método usado é o exaustivo.

- Quando o conjunto está ordenado, existem vários métodos, como os de

- pesquisa sequencial e

- pesquisa binária.

- No que se segue, considera-se que a ordenação é crescente.


Pesquisa Exaustiva 3/34

Pesquisa Exaustiva

Ideia

- Consiste em percorrer sequencialmente todo o conjunto (desde o primeiro até

ao último), até

- se encontrar o elemento procurado, ou

- analisando todos os elementos, concluindo-se que não existe o elemento procurado



Algoritmo

Pesquisar o elemento Elem no vetor V com N elementos

pos -1 // significa que Elem não foi encontrado em V

k 0

Enquanto (k < N) e (pos = -1) Fazer

Se (V[k] = Elem) então

pos k

senão

k k + 1

Se (pos = -1) então

Elem não se encontra em V

senão

encontra-se na posição pos



Função (versão 1)

int PesquisaExaustiva (int Elem, int V[], int N) {

int k = 0, pos = -1; // pos = posição onde se encontra Elem em V

while ( (k < N) && (pos == -1) )

if (Elem == V[k])

pos = k;

else

k = k + 1;

if (pos == -1)

return -1;

else

return pos;

}





int k = 0, pos = -1; // k = posição onde se encontra Elem em V

while ( (k < N) && (pos == -1) )

if (Elem == V[k])

pos = k;

else

k = k + 1;

if (pos == -1)

return -1;

else

return pos;

return pos;

}





int k = 0;

while ( (k < N) && (Elem != V[k]) )

k = k + 1;

if (k == N)

return -1;

else

return k;

}


Pesquisa Sequencial 8/34

Pesquisa Sequencial

Ideia

- Percorrer o vetor desde o primeiro elemento até

- encontrar o elemento procurado (concluindo-se que existe);

- encontrar um elemento maior (quando ordenado crescentemente) que o elemento

procurado ( concluindo-se que não existe);

- analisar todos os elementos do vetor (concluindo-se que não existe)



Algoritmo


pos -1 // significa que Elem ainda não foi encontrado em V

k 0 // percorre os índices dos elementos do vetor V

Enquanto (k < N) e (pos = -1) Fazer

Se (V[k] = Elem) então

pos k

senão Se (V[k] < Elem) então

k k + 1

senão

pos -2; // significa que Elem não está em V

Se (pos ≥ 0) então

Elem encontra-se na posição pos

senão





int PesquisaSequencial (int Elem, int V[], int N) {

int k = 0, pos = -1; // pos = posição onde se encontra Elem em V

while ( (k < N) && (pos == -1) )

if (Elem == V[k])

pos = k;

else

if (V[k] < Elem)

k = k + 1;

else

pos = -2;

return pos;

}




int PesquisaSequencial (int Elem, int V[], int N) {

int k = 0;

while ( (k < N) && (V[k] < Elem) )

k = k + 1;

if ( (k < N) && (Elem == V[k]) )

return k;

else

return -1;

}



Análise de complexidade (eficiência)

- Eficiência temporal:

- A operação realizada mais vezes é o teste da condição de continuidade do ciclo

while, que é no máximo n+1 vezes (no caso de não encontrar x — o pior caso)

- Se x existir no vetor V, o teste é realizado aproximadamente

- n/2 vezes (no caso médio) e,

- 1 vez (no melhor caso)

- Logo, T(n) = O(n) (linear) no pior caso e no caso médio




- Eficiência espacial:

- Gasta o espaço das variáveis locais (incluindo argumentos)

- Como os vetores são passados “por referência” (na linguagem C, o que é passado é o

endereço do primeiro elemento do vetor), o espaço ocupado pelas variáveis locais é

constante e independente do tamanho do vetor

- Logo, S(n) = O(1) (constante) em qualquer caso


Pesquisa Binária 14/34

Pesquisa Binária

Ideia

- Comparar o elemento a pesquisar com o elemento que está ao meio do vetor e

analisar 3 situações diferentes:

- se aquele elemento é igual ao que está ao meio,

- se aquele elemento está antes do meio (é menor ao do meio),

- se aquele elemento está depois do meio (é maior ao do meio).

- Se aconteceu a 1ª situação, então foi encontrado o elemento e está no vetor

naquela posição.

- Se aconteceu a 2ª situação, então basta pesquisar aquele elemento no sub-

vetor até ao meio.

- Se aconteceu a 3ª situação, então basta pesquisar aquele elemento no sub-

vetor do meio para a frente


Pesquisa Binária – versão iterativa 15/34

Pesquisa Binária – versão iterativa

Algoritmo


inicio 0

fim N - 1

pos -1 // pos recebe a posição de Elem (no início assume-se que não existe)

Enquanto ( (inicio ≤ fim) e (pos = -1) ) Fazer

meio (inicio + fim) / 2

Se (Elem = V[meio]) então

pos meio

senão

Se (Elem < V[meio]) então

fim meio – 1

senão

inicio meio + 1



Algoritmo (cont.)

Se (pos ≥ 0) então

Elem encontra-se em V na posição pos

Senão




Função

int PesquisaBinaria (int Elem, int V[], int N) {

int inicio = 0, fim = N – 1, meio, pos = -1;

while ((inicio <= fim) && (pos == -1)) {

meio = (inicio + fim) / 2;

if (Elem == V[meio])

pos = meio;

else

if (Elem < V[meio])

fim = meio - 1;

else

inicio = meio + 1;

}

return pos;

}



Exemplo 1

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

3 7 20 25 26 28 30 34 42 44 50 60 68 72 78 81 85 89 92 99

- Valor a pesquisar: 34



Exemplo 1 (cont.)

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

3 7 20 25 26 28 30 34 42 44 50 60 68 72 78 81 85 89 92 99


- 1ª tentativa:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

3 7 20 25 26 28 30 34 42 44 50 60 68 72 78 81 85 89 92 99

inicio meio fim



Exemplo 1 (cont.)

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

3 7 20 25 26 28 30 34 42 44 50 60 68 72 78 81 85 89 92 99


- 2ª tentativa:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

3 7 20 25 26 28 30 34 42 44 50 60 68 72 78 81 85 89 92 99

inicio meio fim



Exemplo 1 (cont.)

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

3 7 20 25 26 28 30 34 42 44 50 60 68 72 78 81 85 89 92 99


- 3ª tentativa:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

3 7 20 25 26 28 30 34 42 44 50 60 68 72 78 81 85 89 92 99

inicio meio fim



Exemplo 1 (cont.)

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

3 7 20 25 26 28 30 34 42 44 50 60 68 72 78 81 85 89 92 99


- 4ª tentativa:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

3 7 20 25 26 28 30 34 42 44 50 60 68 72 78 81 85 89 92 99

inicio fim

meio



Exemplo 1 (cont.)

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

3 7 20 25 26 28 30 34 42 44 50 60 68 72 78 81 85 89 92 99


- 4ª tentativa:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

3 7 20 25 26 28 30 34 42 44 50 60 68 72 78 81 85 89 92 99

inicio fim

meio

O elemento 34 foi encontrado após 4 tentativas



Exemplo 2

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

3 7 20 25 26 28 30 34 42 44 50 60 68 72 78 81 85 89 92 99




Exemplo 2 (cont.)

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

3 7 20 25 26 28 30 34 42 44 50 60 68 72 78 81 85 89 92 99


- 1ª tentativa:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

3 7 20 25 26 28 30 34 42 44 50 60 68 72 78 81 85 89 92 99

inicio meio fim



Exemplo 2 (cont.)

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

3 7 20 25 26 28 30 34 42 44 50 60 68 72 78 81 85 89 92 99


- 2ª tentativa:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

3 7 20 25 26 28 30 34 42 44 50 60 68 72 78 81 85 89 92 99

inicio meio fim



Exemplo 2 (cont.)

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

3 7 20 25 26 28 30 34 42 44 50 60 68 72 78 81 85 89 92 99


- 3ª tentativa:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

3 7 20 25 26 28 30 34 42 44 50 60 68 72 78 81 85 89 92 99

inicio meio fim



Exemplo 2 (cont.)

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

3 7 20 25 26 28 30 34 42 44 50 60 68 72 78 81 85 89 92 99


- 4ª tentativa:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

3 7 20 25 26 28 30 34 42 44 50 60 68 72 78 81 85 89 92 99

inicio fim

meio



Exemplo 2 (cont.)

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

3 7 20 25 26 28 30 34 42 44 50 60 68 72 78 81 85 89 92 99


- 5ª tentativa:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

3 7 20 25 26 28 30 34 42 44 50 60 68 72 78 81 85 89 92 99

inicio

fim

meio



Exemplo 2 (cont.)

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

3 7 20 25 26 28 30 34 42 44 50 60 68 72 78 81 85 89 92 99


- 6ª tentativa:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

3 7 20 25 26 28 30 34 42 44 50 60 68 72 78 81 85 89 92 99

fim inicio

meio



Exemplo 2 (cont.)

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

3 7 20 25 26 28 30 34 42 44 50 60 68 72 78 81 85 89 92 99


- 6ª tentativa:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

3 7 20 25 26 28 30 34 42 44 50 60 68 72 78 81 85 89 92 99

fim inicio

meio

O elemento 40 não está na lista,

o que se concluiu após 6 tentativas (fim > inicio)




Eficiência temporal:

- Em cada iteração, o tamanho do sub-vetor a analisar é dividido

por um fator de aproximadamente igual a 2

- Ao fim de k iterações,

o tamanho do sub-vetor a analisar é aproximadamente igual a n/2k

- Se não existir no vetor o valor procurado, o ciclo só termina quando:

n/2k 1 log2 n - k 0 k log2 n

- No pior caso, o número de iterações é aproximadamente igual a log2 n.

Logo, T(n) = O(log n) (logarítmico)


Pesquisa Binária – versão recursiva 33/34

Pesquisa Binária – versão recursiva

Algoritmo

- Pesquisar Elem no vetor V entre as posições inicio e fim

Se (inicio > fim) então

Devolver (-1) // significa que Elem não está em V

meio = (inicio + fim) / 2

Se (Elem = V[meio]) então

Devolver (meio) // significa que Elem está em V na posição meio

Se (Elem < V[meio]) então

Pesquisar Elem no vetor V entre as posições inicio e (meio - 1)

Senão

Pesquisar Elem no vetor V entre as posições (meio + 1) e fim


Pesquisa Binária – versão recursiva 34/34

Função

int PesquisaBinariaRec (int Elem, int V[], int inicio, int fim) {

int meio;

if (inicio > fim)

return -1; // Elem não está em V

meio = (inicio + fim) / 2;

if (Elem == V[meio])

return meio; // Elem está na posição meio

if (Elem < V[meio])

return PesquisaBinariaRec(Elem, V, inicio, meio - 1);

else

return PesquisaBinariaRec(Elem, V, meio + 1, fim);

}


Documents

ALGORITMOS DE PESQUISA - di.ubi.ptcbarrico/Disciplinas/ProgramacaoAlgoritmos/... · Algoritmos de Pesquisa Programação II. Pesquisa Binária – versão iterativa 15/34 Pesquisa