Programação II
Laboratório II
Prof. Mateus Raeder
Transparências baseadas nos originais
da Prof. Patrícia Jaques
Universidade do Vale do Rio dos Sinos
- São Leopoldo -
Pesquisa de Dados em Tabelas
• Métodos para localizar entradas em tabelas, dado o valor
de uma chave primária como argumento de pesquisa
Chave Primária
Info
1
7
...
2
9
...
3
14
...
4
35
...
5
78
...
– Localizar: informações relativa às chaves: 35, 12
Programação II – Prof. Mateus Raeder
Técnica para Pesquisa Sequencial
• Fazer uma varredura serial da tabela,
comparando o argumento de pesquisa com a
chave de cada entrada, até ser encontrada
uma que seja igual (sucesso) ou até que seja
atingido o final da tabela (não foi
encontrado).
Programação II – Prof. Mateus Raeder
Pesquisa Serial em
Tabela não ordenada
public static int pesquisaSequencial (int tab[], int arg) {
int i = 0;
while (i < tab.length) {
if (tab[i] == arg) return i;
else i = i + 1;
}
return -1;
}
Exemplo: procurando chave 4
Programação II – Prof. Mateus Raeder
Pesquisa Serial em
Tabela ordenada
public static int pesquisaSequencialOrdenada
(int tab[], int arg) {
int i = 0;
while ((i < tab.length) && (tab[i]<= arg)) {
if (tab[i] == arg) return i;
else i = i + 1;
}
return -1;
}
Exemplo: procurando chave 11
Programação II – Prof. Mateus Raeder
Pesquisa Sequencial
• Método mais simples
• Intuitivo
Programação II – Prof. Mateus Raeder
Exercício:
• Fazer um algoritmo para Pesquisa Sequencial de
uma tabela (ordenada e não ordenada),
considerando a tabela como uma lista
encadeada.
Programação II – Prof. Mateus Raeder
Pesquisa Binária
• Método para ser aplicado em tabelas ordenadas
• Reduz o nro. de elementos a serem considerados
pela metade
• Exemplo: Pesquisa de chave com valor 17
1
2
Programação II – Prof. Mateus Raeder
Pesquisa Binária
• Técnica
– Consiste na comparação do argumento de pesquisa (arg)
com a chave da entrada localizada no endereço médio
da tabela.
– Se arg for maior do que a chave contida naquele
endereço, o processo é repetido para a metade superior
da tabela, e
– se for menor, para a metade inferior.
– Se for igual, a busca se encerra com sucesso.
• A área de pesquisa é reduzida à metade do
número de elementos a cada vez
Programação II – Prof. Mateus Raeder
Exemplo pesquisa binária (1)
Argumento de pesquisa: 032
E:
C:
O:
0
002
1
015
2
017
3
030
4
032
5
034
6
040
7
050
  

2ª
1ª
4ª
3ª
8
080
9
090
10
095
11
097
12
099
13
101
E: endereços
C: chaves
O: ordem de exame das entradas
Programação II – Prof. Mateus Raeder
14
105
Exemplo pesquisa binária (2)
Argumento de pesquisa: 54
E:
C:
0
1
21
21
32
32
43
43
54
4
5
5
6
6
7
7
8
8
9
9
10
65
76
87
98
109 200
   
O:
2ª
3ª
4ª
1ª
Programação II – Prof. Mateus Raeder
Exemplo pesquisa binária (3)
Argumento de pesquisa: 100
E:
C:
O:
01
12
23
34
4
5
5
6
67
7
8
21
32
43
54
65
76
87
98
8
9
9
10
109 200

 
1ª
2ª
3ª
Programação II – Prof. Mateus Raeder
Algoritmo Pesquisa Binária
• Localizar, por busca binária, a posição
ocupada pela chave de valor arg em um
vetor tab, ordenado com reorganização
física
Parâmetros:
tab: tabela onde será feita a pesquisa
arg: argumento de pesquisa
Retorno : -1
não encontrou
 -1 chave está na posição
Programação II – Prof. Mateus Raeder
Algoritmo Pesquisa Binária
public static int pesquisaBinaria (int tab[], int arg) {
int inf, sup, med;
inf = 0; sup = tab.length-1;
while (inf <= sup) {
med = (inf + sup)/2; //divisão inteira
if (arg == tab[med]) return med;
else if (arg > tab[med]) inf = med + 1; // procura na 2a. metade
else if (arg < tab[med]) sup = med - 1; // procura na 1ª metade
}
return -1;
}
Exemplo: busca da chave 43
inf
E:
C:
O:
inf sup
sup
inf
01
1
2
2
3
3
4
4
5
56
6
7
78
21
32
43
54
65
76
87
98
2º 3º
3º
89
9
10
109 200
Programação II – Prof. Mateus Raeder
1º
Procedimento Recursivo
para Pesquisa Binária
public static int pesquisaBinariaR (int tab[], int arg) {
return pesquisaBinariaR (tab, arg, 0, tab.length-1);
}
private static int pesquisaBinariaR (int tab[], int arg, int inf, int sup) {
int med;
if (inf > sup) return -1;
med = (inf + sup)/2; //divisão inteira
if (arg == tab[med]) return med;
else if (arg > tab[med])
return pesquisaBinariaR(tab, arg, med + 1, sup);
else return pesquisaBinariaR (tab, arg, inf, med - 1);
}
Programação II – Prof. Mateus Raeder