2 Lista
1176 palavras
5 páginas
Nome: Jorge Seiji Takamori RA: 6656412085 5ºCCS2º Lista: Busca Sequencial e Binaria 1. Calcule o número de comparações para o pior caso necessárias para localizar uma entrada para pesquisa sequencial e pesquisa binária, para tabelas com:
a) 32 entradas
Sequencial = 32 comparações
Binária = log2 32 = 5 comparações
b) 128 entradas
Sequencial = 128 comparações
Binária = log2 128 = 7 comparações
c) 2048 entradas
Sequencial = 2048 comparações
Binária = log2 2048 = 11 comparações
d) 16384 entradas
Sequencial = 16384 comparações
Binária = log2 16384 = 14 comparações
2. Considere o vetor s = [12, 25, 33, 37, 48, 57, 86, 92]. Mostre todos os passos do algoritmo de pesquisa binária quando está sendo pesquisado o número
a) 25
12
25
33
37
48
57
68
92 esq meio
dir
25 == V[3]
25 == 37 Falso
25 < 37 Verdadeiro
12
25
33
37
48
57
68
92
esq meio dir
25 == V[1]
25 == 25 Verdadeiro
b) 10
12
25
33
37
48
57
68
92
esq
meio
dir
10 == V[3]
10 ==37 Falso
10 < 37 Verdadeiro
12
25
33
37
48
57
68
92
esq meio dir
10 == V[2]
10 == 25 Falso
10 < 25 Verdadeiro
meio
12
25
33
37
48
57
68
92
Esq Dir
10 == V[0] Falso
10 == 12 Falso
Número não existe no vetor
3. Considere a seguinte tabela ordenada:
2 5 7 11 13 17 25
a) Diga quantas comparações serão necessárias para procurar cada um dos 7 elementos da tabela?
2
5
7
11
13
17
25
meio
11 == 11
1 comparação
2
5
7
11
13
17
25
meio
2
5
7
11
13
17
25
Esq
meio
Dir
2
5
7
11
13
17
25
meio
7 == 7
3 comparações
2
5
7
11
13
17
25
meio
2
5
7
11
13
17
25
meio
5 == 5
2 comparações
2
5
7
11
13
17
25
meio
2
5
7
11
13
17
25
Esq
meio
Dir
2
5
7
11
13
17
25 meio 2 == 2
3 comparações
2
5
7
11
13
17
25
meio
2
5
7
11
13
17
25
meio
17 == 17
2 comparações
2
5
7
11
13
17
25
meio
2
5
7
11
13
17
25
Esq meio Dir
2
5
7
11
13
17
25
meio
13 == 13
3 comparações
2
5
7
11
13
17
25
meio
2
5
7
11
13
17
25