Aula_007 - Algoritmos de Busca

Prévia do material em texto

1
Aula 7
Professores:
Dante Corbucci Filho
Alexandre Plastino
Conteúdo:
- Algoritmos de Busca
 - Busca Simples
 - Busca com Sentinela
 - Busca Binária
 - Busca do Maior e Menor elementos
 - Noções de Complexidade de Algoritmos
2
Algoritmos de Busca
 O problema de busca é caracterizado pela 
procura de um determinado elemento em um grupo de 
elementos do mesmo tipo.
 Exemplos:
 - encontrar o registro de um cliente entre todos os 
registros dos clientes de um banco, para que seja possível 
informar seu saldo.
 - encontrar o registro de um aluno dentre todos os 
registros dos alunos de uma universidade, para que seja possível 
gerar o seu histórico escolar.
3
Algoritmos de Busca
 Algoritmos de busca visam resolver o problema 
da busca e são, portanto, bastante utilizados em 
computação.
 Necessita-se então de algoritmos eficientes de 
busca. De forma simplificada, um algoritmo eficiente é 
aquele que realiza sua tarefa em tempo 
computacional reduzido.
4
Algoritmos de Busca
 É claro que o tempo de execução de um 
algoritmo de busca depende do tamanho do conjunto 
de elementos a serem consultados. É mais rápido 
procurar um elemento em um grupo de 100 do que em 
um grupo de 100.000.
 Além disso, a eficiência do processo de busca 
depende do algoritmo adotado. Exploraremos o 
conceito de complexidade de algoritmos no sentido de 
tentar avaliar a eficiência dos algoritmos estudados.
5
Algoritmos de Busca
 O problema de busca é caracterizado pela procura de um 
determinado elemento em um grupo de elementos do mesmo 
tipo.
 Sem perda de generalidade, o problema será atacado 
considerando-se que:
 - os elementos a serem percorridos são numéricos, distintos
 e estão armazenados em um vetor (array);
 - o número de elementos define o tamanho do vetor;
 - o elemento procurado pode não estar no vetor (no 
 conjunto de elementos).
6
Algoritmos de Busca
Vetor: contém o grupo de elementos 
1 2 3 4 5 6 7 8 9 10
7 19 4 10 18 6 8 1 3 12
Exemplo 2) Elemento procurado: 9 Resposta: não encontrado 
Exemplo 1) Elemento procurado: 18 Resposta: posição 5 
posição dos elementos
(índices) 
tamanho do vetor 
(número de elementos: N)
7
Program Busca (input{teclado}, output{vídeo});
Const 
 N = 100;
Type
 T_Dominio = 1 . . N;
 T_Vetor = array[T_Dominio] of integer;
Var
 Numeros: T_Vetor;
 Dado: Integer; {elemento procurado}
 Posicao: Integer ; {posição encontrada}
Begin 
End. 
8
Program Busca (input{teclado}, output{vídeo});
Const 
 N = 100;
Type
 T_Dominio = 1 . . N;
 T_Vetor = array[T_Dominio] of Integer;
Var
 Numeros: T_Vetor;
 Dado: Integer; {elemento procurado}
 Posicao: Integer; {posição encontrada}
Begin 
 Ler(Numeros, Dado);
 Posicao:= BuscaElemento(Numeros, Dado);
 Escrever(Posicao);
End. 
9
Program Busca (input{teclado}, output{vídeo});
. . .
Procedure Ler(Var V{s}: T_Vetor; Var X{s}: Integer); 
 begin 
 end;
Function BuscaElemento(V{e}: T_Vetor; X{e}:Integer): Integer; 
 begin 
 end;
Procedure Escrever(Pos{e}: Integer); 
 begin 
 end;
Begin 
 Ler(Numeros, Dado);
 Posicao := BuscaElemento(Numeros, Dado);
 Escrever(Posicao);
End. 
10
Program Busca (input{teclado}, output{vídeo});
. . .
Procedure Ler(Var V{s}: T_Vetor; Var X{s}: integer); 
 var ind: T_Dominio;
 begin 
 for ind:= 1 to N do
 begin
 write(output, ’Elemento[’, Ind, ’]= ’);
 readln(input, V[Ind]); 
 end;
 write(output, ’Elemento procurado= ’);
 readln(input, X);
 end;
. . .
Begin 
 Ler(Numeros, Dado);
 Posicao:= BuscaElemento(Numeros, Dado);
 Escrever(Posicao);
End. 
11
Program Busca (input{teclado}, output{vídeo});
. . .
Procedure Escrever(Pos{e}: Integer); 
 begin 
 if Pos>0 then
 writeln(output, ’A posicao do elemento é’, Pos)
 else
 writeln(output, ’O elemento não foi encontrado.’)
 end;
. . .
Begin 
 Ler(Numeros, Dado);
 Posicao := BuscaElemento(Numeros, Dado);
 Escrever(Posicao);
End. 
12
Busca Simples (for-do)
Vetor: contém o grupo de elementos 
1 2 3 4 5 6 7 8 9 10
7 19 4 10 18 6 8 1 3 12
 Todas as N posições do vetor são comparadas com o 
valor procurado. 
Elemento procurado: 18 
Posição: 0 
13
Busca Simples (for-do)
Vetor: contém o grupo de elementos 
1 2 3 4 5 6 7 8 9 10
7 19 4 10 18 6 8 1 3 12
 Todas as N posições do vetor são comparadas com o 
valor procurado. 
Elemento procurado: 18 
Posição: 1
14
Busca Simples (for-do)
Vetor: contém o grupo de elementos 
1 2 3 4 5 6 7 8 9 10
7 19 4 10 18 6 8 1 3 12
 Todas as N posições do vetor são comparadas com o 
valor procurado. 
Elemento procurado: 18 
Posição: 2
15
Busca Simples (for-do)
Vetor: contém o grupo de elementos 
1 2 3 4 5 6 7 8 9 10
7 19 4 10 18 6 8 1 3 12
 Todas as N posições do vetor são comparadas com o 
valor procurado. 
Elemento procurado: 18 
Posição: 3
16
Busca Simples (for-do)
Vetor: contém o grupo de elementos 
1 2 3 4 5 6 7 8 9 10
7 19 4 10 18 6 8 1 3 12
 Todas as N posições do vetor são comparadas com o 
valor procurado. 
Elemento procurado: 18 
Posição: 4
17
Busca Simples (for-do)
Vetor: contém o grupo de elementos 
1 2 3 4 5 6 7 8 9 10
7 19 4 10 18 6 8 1 3 12
 Todas as N posições do vetor são comparadas com o 
valor procurado. 
Elemento procurado: 18 
Posição: 5
18
Busca Simples (for-do)
Vetor: contém o grupo de elementos 
1 2 3 4 5 6 7 8 9 10
7 19 4 10 18 6 8 1 3 12
 Todas as N posições do vetor são comparadas com o 
valor procurado. 
Elemento procurado: 18 
Posição: 5
19
Busca Simples (for-do)
Vetor: contém o grupo de elementos 
1 2 3 4 5 6 7 8 9 10
7 19 4 10 18 6 8 1 3 12
 Todas as N posições do vetor são comparadas com o 
valor procurado. 
Elemento procurado: 18 
Posição: 5
20
Busca Simples (for-do)
Vetor: contém o grupo de elementos 
1 2 3 4 5 6 7 8 9 10
7 19 4 10 18 6 8 1 3 12
 Todas as N posições do vetor são comparadas com o 
valor procurado. 
Elemento procurado: 18 
Posição: 5
21
Busca Simples (for-do)
Vetor: contém o grupo de elementos 
1 2 3 4 5 6 7 8 9 10
7 19 4 10 18 6 8 1 3 12
 Todas as N posições do vetor são comparadas com o 
valor procurado. 
Elemento procurado: 18 
Posição: 5
22
Busca Simples (for-do)
Vetor: contém o grupo de elementos 
1 2 3 4 5 6 7 8 9 10
7 19 4 10 18 6 8 1 3 12
 Todas as N posições do vetor são comparadas com o 
valor procurado. 
Elemento procurado: 18 
Posição: 5
23
Busca Simples (for-do)
Vetor: contém o grupo de elementos 
1 2 3 4 5 6 7 8 9 10
7 19 4 10 18 6 8 1 3 12
 Todas as N posições do vetor são comparadas com o 
valor procurado. 
Elemento procurado: 18 
Posição: 5 Resultado
24
Program Busca (input{teclado}, output{vídeo});
. . . 
Function BuscaElemento(V{e}: T_Vetor; X{e}: Integer): Integer;
 var ind, pos: Integer; { Busca Simples (for-do) }
 begin
 pos:=0;
 for ind:= 1 to N do
 if V[ind] = X then
 pos:=ind;
 BuscaElemento:=pos;
 end;. . .
Begin 
 Ler(Numeros, Dado);
 Posicao := BuscaElemento(Numeros, Dado);
 Escrever(Posicao);
End. 
25
Busca Simples (for-do)
 Todas as N posições do vetor são 
comparadas com o valor procurado, mesmo quando 
este é encontrado antes do fim do vetor.
 Nitidamente, esta é uma busca ineficiente.
 O algoritmo avalia necessariamente N 
elementos. Portanto, sua complexidade é da ordem 
de N, representado por O(N).
26
Busca Simples (while-do)
Vetor: contém o grupo de elementos 
1 2 3 4 5 6 7 8 9 10
7 19 4 10 18 6 8 1 3 12
 Neste algoritmo, o processo de busca é interrompido 
quando o elemento procurado é encontrado. 
Elemento procurado: 4
Posição: 0 
27
Busca Simples (while-do)
Vetor: contém o grupo de elementos 
1 2 3 4 5 6 7 8 9 10
7 19 4 10 18 6 8 1 3 12
 Neste algoritmo, o processo de busca é interrompido 
quando o elemento procurado é encontrado. 
Elemento procurado: 4
Posição: 0 
28
Busca Simples (while-do)
Vetor: contém o grupo de elementos 
1 2 3 4 5 6 7 8 9 10
7 19 4 10 18 6 8 1 3 12
 Neste algoritmo, o processo de busca é interrompido 
quando o elemento procurado é encontrado. 
Elemento procurado: 4
Posição: 0 
29
Busca Simples (while-do)
Vetor: contém o grupo de elementos 
1 2 3 4 5 6 7 8 9 10
7 19 4 10 18 6 8 1 3 12
 Neste algoritmo, o processo de busca é interrompido 
quando o elemento procurado é encontrado. 
Elemento procurado: 4
Posição: 3
30
Busca Simples (while-do)
Vetor: contém o grupo de elementos 
1 2 3 4 5 6 7 8 9 10
7 19 4 10 18 6 8 1 3 12
 Neste algoritmo, o processo de busca é interrompido 
quando o elemento procurado é encontrado. 
Elemento procurado: 4
Posição: 3 Resultado
31
Program Busca (input{teclado}, output{vídeo});
. . .
Function BuscaElemento(V{e}: T_Vetor; X{e}:integer): Integer;
 var ind, pos: Integer; { Busca Simples (while-do) }
 begin
 pos:=0; 
 ind:=1;
 while ind<=N do
 if V[ind]<>X then ind:=ind+1
 else
 begin
 pos:=ind;
 ind:=N+1 {força saída}
 end; 
 BuscaElemento:=pos;
 end;
. . .
32
Busca Simples (while-do)
 Em média, este algoritmo executa N/2 vezes o corpo 
do comando while-do. Em algumas vezes, o dado será 
encontrado logo na primeira posição, em outras, na última 
posição.
 No pior caso, o algoritmo avalia N elementos. 
Portanto, sua complexidade também é da ordem de N, 
representado por O(N).
33
Busca com Sentinela (while-do)
 O algoritmo anterior poderia executar menos comparações, 
se não houvesse a necessidade de evitar ultrapassar o fim do vetor, 
caso o elemento procurado não se encontre no conjunto. 
 Propõe-se então alocar uma posição a mais no vetor e 
inserir forçadamente o elemento procurado nesta posição. 
 Desta forma, necessariamente o elemento procurado será 
encontrado. Se for encontrado na posição N+1, significa que o 
elemento não pertence ao conjunto original.
 Apesar de executar menos comparações, o algoritmo avalia, 
no pior caso, N+1 elementos. Portanto, sua complexidade também é 
da ordem de N, representado por O(N).
34
Program Busca (input{teclado}, output{vídeo});
Const 
 N = 100;
Type
 T_Dominio = 1 . . N+1; { Uma posição a mais }
 T_Vetor = array[T_Dominio] of integer;
. . .
Function BuscaElemento(V{e}: T_Vetor; X{e}: Integer): Integer;
 var ind, pos: Integer; { Busca com Sentinela (while-do) }
 begin
 ind:=1;
 while V[ind]<>x do
 ind:=ind+1;
 if ind<=N then pos:=ind
 else pos:=0;
 BuscaElemento:=pos
 end;
. . .
35
Busca Binária
 Os algoritmos apresentados até o momento foram
projetados sem levar em consideração se os elementos do 
vetor encontram-se ordenados ou não.
 Caso os elementos se encontrem ordenados, um 
algoritmo mais eficiente pode ser implementado.
 Este algoritmo, chamado busca binária, a cada passo
divide o espaço de busca em dois até encontrar o elemento 
sendo procurado.
36
Busca Binária
Os N elementos encontram-se ordenados no vetor.
Vetor
Início Fim
Elemento procurado: 14
1 3 4 5 7 8 9 10 12 13 14 15 17 18 19 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
37
Busca Binária
Vetor
Início Fim
14 > 10
Número de elementos comparados: 1
Elemento procurado: 14
Meio
1 3 4 5 7 8 9 10 12 13 14 15 17 18 19 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
38
Busca Binária
Vetor
Fim
Número de elementos comparados: 1
Elemento procurado: 14
Início
Meio
1 3 4 5 7 8 9 10 12 13 14 15 17 18 19 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
39
Busca Binária
Vetor
Fim
Número de elementos comparados: 2
Elemento procurado: 14
MeioInício
14 < 15
1 3 4 5 7 8 9 10 12 13 14 15 17 18 19 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
40
Busca Binária
Vetor
Fim
Número de elementos comparados: 2
Elemento procurado: 14
Início
1 3 4 5 7 8 9 10 12 13 14 15 17 18 19 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
41
Busca Binária
Vetor
Fim
Número de elementos comparados: 3
Elemento procurado: 14
Início
14 > 13
Meio
1 3 4 5 7 8 9 10 12 13 14 15 17 18 19 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
42
Busca Binária
Vetor
Número de elementos comparados: 3
Elemento procurado: 14
Início Fim
1 3 4 5 7 8 9 10 12 13 14 15 17 18 19 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
43
Busca Binária
Vetor
Número de elementos comparados: 4
Elemento procurado: 14
Início Fim
14 = 14
Meio
1 3 4 5 7 8 9 10 12 13 14 15 17 18 19 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
44
Busca Binária
Vetor
Número de elementos comparados: 4
Elemento procurado: 14
Início Fim
14 = 14
MeioResposta: Posição = 11
1 3 4 5 7 8 9 10 12 13 14 15 17 18 19 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
45
Function BuscaElemento(V{e}: T_Vetor; X{e}: Integer): Integer;
 
 var inicio, meio, fim: T_Dominio; { Busca Binária }
 begin
 inicio:= 1; 
 fim:= N; 
 meio := (inicio + fim) div 2;
 while (X<>V[meio]) and (inicio<>fim) do
 begin
 if X>V[meio] then inicio := meio + 1
 else fim := meio -1;
 meio := (inicio + fim) div 2
 end;
 if X<>V[meio] then BuscaElemento := 0 
 else BuscaElemento := meio;
 end;
46
Busca Binária
 Na busca binária, a cada passo, divide-se o espaço de 
busca em dois até que o elemento procurado seja encontrado.
 Considerando-se um vetor de 16 posições, no máximo 4 
divisões podem ser feitas. E portanto, no máximo 4 elementos do 
vetor serão comparados com o elemento procurado.
 Observe que se o vetor for de 32 posições (vetor duplicado), 
no máximo 5 elementos do vetor serão acessados (apenas um a 
mais). Ou ainda, se o vetor tiver 32.000 posições, apenas 15 
avaliações serão necessárias.
 Na prática, se o vetor tiver N posições, a busca binária 
avaliará, no pior caso, log2(N) elementos. Portanto, sua 
complexidade é da ordem de log(N), representado por O(log(N)). 
Busca Simples (While-do)
ExecutávelCódigo Fonte
Busca Simples (For-do)
ExecutávelCódigo Fonte
Busca Binária
ExecutávelCódigo Fonte
Busca com Sentinela
ExecutávelCódigo Fonte
47Busca do Maior e Menor Elementos
 Este problema é caracterizado pela procura do maior 
e do menor elementos em um grupo de elementos do mesmo 
tipo.
 Sem perda de generalidade, o problema será atacado 
considerando-se que:
- os elementos a serem percorridos são numéricos,
 e estão armazenados em um vetor (array);
- estes elementos podem não ser distintos;
- o número de elementos define o tamanho do vetor.
 
48
Busca do Maior e Menor Elementos
Vetor: contém o grupo de elementos 
1 2 3 4 5 6 7 8 9 10
4 19 4 10 18 6 19 1 3 18
posição dos elementos
(índices) 
tamanho do vetor 
(número de elementos: N)
Resposta: Maior Elemento: 19
 Menor Elemento: 1 
49
Program BuscaMaiorMenor (input{teclado}, output{vídeo});
Const 
 N = 100;
Type
 T_Dominio = 1 . . N;
 T_Vetor = array[T_Dominio] of integer;
Var
 Numeros: T_Vetor;
 Maior: integer; {conterá o maior elemento}
 Menor: integer; {conterá o menor elemento}
Begin 
End. 
50
Program BuscaMaiorMenor (input{teclado}, output{vídeo});
Const 
 N = 100;
Type
 T_Dominio = 1 . . N;
 T_Vetor = array[T_Dominio] of integer;
Var
 Numeros: T_Vetor;
 Maior: integer; {conterá o maior elemento}
 Menor: integer; {conterá o menor elemento}
Begin 
 Ler(Numeros);
 BuscaMaiorMenorElemento(Numeros, Maior, Menor);
 Escrever(Maior, Menor);
End. 
51
Program BuscaMaiorMenor (input{teclado}, output{vídeo});
. . .
Procedure Ler(Var V{s}: T_Vetor); 
 begin 
 end;
Procedure BuscaMaiorMenorElementos(V{e}: T_Vetor; 
 var maior{s}, menor{s}: integer); 
 begin 
 end;
Procedure Escrever(maior{e}, menor{e}: integer); 
 begin 
 end;
Begin 
 Ler(Numeros);
 BuscaMaiorMenorElementos(Numeros,Maior,Menor);
 Escrever(Maior,Menor);
End.
52
Program BuscaMaiorMenor (input{teclado}, output{vídeo});
. . .
Procedure Ler(Var V{s}: T_Vetor); 
 var ind: T_Dominio;
 begin 
 for ind:= 1 to N do
 begin
 write(output, ’Elemento[’, Ind, ’]= ’);
 readln(input, V[Ind]); 
 end
 end;
. . .
Begin 
 Ler(Numeros);
 BuscaMaiorMenorElementos(Numeros,Maior,Menor);
 Escrever(Maior,Menor);
End.
53
Program BuscaMaiorMenor (input{teclado}, output{vídeo});
. . .
Procedure Escrever(maior{e}, menor{e}: integer); 
 begin 
 writeln(output, ’O maior elemento é ’, maior);
 writeln(output, ’O menor elemento é ’, menor);
 end;
. . .
Begin
 Ler(Numeros);
 BuscaMaiorMenorElementos(Numeros,Maior,Menor);
 Escrever(Maior,Menor);
End.
54
Program BuscaMaiorMenor (input{teclado}, output{vídeo});
. . . 
Procedure BuscaMaiorMenorElementos (V{e}: T_Vetor; 
 var maior{s}, menor{s}: integer);
 var ind: T_Dominio; 
 begin
 maior:=V[1]; 
 menor:=V[1];
 for ind:= 2 to N do
 if V[ind] > maior then
 maior:=V[ind]
 else
 if V[ind] < menor then
 menor:=V[ind]
 end;
. . .
Begin
 Ler(Numeros);
 BuscaMaiorMenorElementos(Numeros, Maior, Menor);
 Escrever(Maior, Menor);
End.
55
Busca do Maior e Menor Elementos
 O algoritmo apresentado encontra o maior 
e o menor elementos em um vetor de N 
elementos.
 Dado que cada um dos N elementos é 
avaliado necessariamente uma vez, a sua 
complexidade é da ordem de N, representado por 
O(N).
Busca do maior e menor elementos
ExecutávelCódigo Fonte
56
Aula 7
Professores:
Dante Corbucci Filho
Alexandre Plastino
Conteúdo:
- Algoritmos de Busca
 - Busca Simples
 - Busca com Sentinela
 - Busca Binária
 - Busca do Maior e Menor elementos
 - Noções de Complexidade de Algoritmos