ALG_II_TEMA_09

Prévia do material em texto

UNICARIOCA
TEMA-09
PESQUISA BINÁRIA
ALGORITMOS-II
PESQUISA BINÁRIA
A pesquisa em tabela pode ser mais eficiente se os dados
estiverem ORDENADOS.
PESQUISA BINÁRIA  IDÉIA BÁSICA
Seja p o valor a ser procurado.
1. Compare p com o valor que está na posição do MEIO da
tabela.
2. Se p é IGUAL ao valor do MEIO da tabela, OK, o valor
procurado foi ENCONTRADO.
3. Se p é MENOR que o valor do MEIO então p está na
PRIMEIRA METADE da tabela.
4. Se p é MAIOR que o valor do MEIO então p está na
SEGUNDA METADE da tabela.
5. Repita o processo até que p seja encontrado, ou fique
apenas um valor que é diferente do procurado, o que
significa uma PESQUISA SEM SUCESSO.
EXEMPLO-01  Pesquisar se o elemento “Rui” ocorre
no seguinte no vetor.
CÁLCULO DO MEIO
MEIO = (ESQ + DIR) Div 2
MEIO = (1 + 8) Div 2= 4 (parte inteira)
P  elemento procurado = RUI
MEIO = 4
P (RUI) = ELEMENTO DO MEIO (EVA) ?
FALSO !
1ª ITERAÇÃO
P (RUI) < ELEMENTO DO MEIO [4] (EVA) ?
FALSO !
PRÓXIMO PASSO
COMO P > ELEMENTO DO MEIO (EVA) ENTÃO P ESTÁ NA
SEGUNDA METADE (PARTE SUPERIOR) DA TABELA !
CÁLCULO DO MEIO
ESQ = MEIO + 1 (4+1 = 5);
MEIO = (ESQ + DIR) DIV 2
MEIO = (5 + 8) DIV 2= 6
2ª ITERAÇÃO
ALGORITMOS-II TEMA_09 1 MANUEL
MEIO = 6
P (RUI) = ELEMENTO DO MEIO (IVO) ?
FALSO !
2ª ITERAÇÃO
P (RUI) < ELEMENTO DO MEIO [6] (IVO) ?
FALSO !
PRÓXIMO PASSO
COMO P > ELEMENTO DO MEIO (IVO) ENTÃO P ESTÁ NA
SEGUNDA METADE (PARTE SUPERIOR) DA TABELA !
CÁLCULO DO MEIO
ESQ = MEIO + 1 (7);
MEIO = (ESQ + DIR) DIV 2
MEIO = (7 + 8) DIV 2= 7
3ª ITERAÇÃO
MEIO = 7
P (RUI) = ELEMENTO DO MEIO (LIA) ?
FALSO !
3ª ITERAÇÃO
P (RUI) = ÚLTIMO ELEMENTO (RUI) ?
VERDADEIRO !
OK  ELEMENTO ENCONTRADO !
4ª ITERAÇÃO
ESQ = MEIO = DIR
UNICARIOCA
TEMA-09
PESQUISA BINÁRIA
ALGORITMOS-II
VÍDEO-02
ALGORITMOS-II TEMA_09 2 MANUEL
EXEMPLO-02  Pesquisar se o valor 21 ocorre no
vetor VET.
CÁLCULO DO MEIO
MEIO = (ESQ + DIR) Div 2
MEIO = (1 + 10) Div 2 = 11/2 = 5,5 = 5 (parte inteira)
VET[5] = 15
P  elemento procurado = 21
VET 1 4 7 8 15 19 21 28 31 37
Posição 1 2 3 4 5 6 7 8 9 10
VET 1 4 7 8 15 19 21 28 31 37
Posição 1 2 3 4 5 6 7 8 9 10
1ª ITERAÇÃO
MEIO = 5 (posição 5)
P (21) = VET[5] (15) ?
FALSO !
VET 1 4 7 8 15 19 21 28 31 37
Posição 1 2 3 4 5 6 7 8 9 10
1ª ITERAÇÃO
P (21) < ELEMENTO DO MEIO VET [5] (15) ?
FALSO !
PRÓXIMO PASSO
COMO P(21) > ELEMENTO DO MEIO (15) ENTÃO P DEVE
ESTÁ NA SEGUNDA METADE (PARTE SUPERIOR) DA
TABELA !
VET 1 4 7 8 15 19 21 28 31 37
Posição 1 2 3 4 5 6 7 8 9 10
2ª ITERAÇÃO
CÁLCULO DO MEIO
MEIO = (ESQ + DIR) Div 2
MEIO = (6 + 10) Div 2 = 16/2 = 8
VET[8] = 28
P  elemento procurado = 21
VET 1 4 7 8 15 19 21 28 31 37
Posição 1 2 3 4 5 6 7 8 9 10
2ª ITERAÇÃO
MEIO = 8 (posição 8)
P (21) = VET[8] (28) ?
FALSO !
VET 1 4 7 8 15 19 21 28 31 37
Posição 1 2 3 4 5 6 7 8 9 10
2ª ITERAÇÃO
P (21) < ELEMENTO DO MEIO VET [8] (28) ?
VERDADEIRO!
PRÓXIMO PASSO
COMO P(21) < ELEMENTO DO MEIO (28) ENTÃO P DEVE
ESTÁ NA PRIMEIRA METADE (PARTE INFERIOR) DA
TABELA !
ALGORITMOS-II TEMA_09 3 MANUEL
VET 1 4 7 8 15 19 21 28 31 37
Posição 1 2 3 4 5 6 7 8 9 10
3ª ITERAÇÃO
CÁLCULO DO MEIO
MEIO = (ESQ + DIR) Div 2
MEIO = (6 + 7) Div 2 = 13/2 = 6,5 = 6  Posição 6 !
VET[6] = 19
P  elemento procurado = 21
VET 1 4 7 8 15 19 21 28 31 37
Posição 1 2 3 4 5 6 7 8 9 10
3ª ITERAÇÃO
MEIO = 6 (posição 8)
P (21) = VET[6] (19) ?
FALSO !
VET 1 4 7 8 15 19 21 28 31 37
Posição 1 2 3 4 5 6 7 8 9 10
3ª ITERAÇÃO
P (21) < ELEMENTO DO MEIO VET [8] (19) ?
FALSO!
PRÓXIMO PASSO
COMO P(21) > ELEMENTO DO MEIO (28) ENTÃO P DEVE
ESTÁ NA SEGUNDA METADE (PARTE SUPERIOR) DA
TABELA !
VET 1 4 7 8 15 19 21 28 31 37
Posição 1 2 3 4 5 6 7 8 9 10
4ª ITERAÇÃO
P (21) = VET[7] = 21 ?
VERDADEIRO !
OK  ELEMENTO ENCONTRADO !
POSIÇÃO = MEIO = 7 !
ESQ = DIR = MEIO = 7
//PESQUISA BINÁRIA
ALGORITMO
Var VET:ARRAY[1..10] de inteiro;
i,inicio,fim,meio,busca: inteiro;
achou: lógico; (V/F)
INÍCIO
// Leitura do vetor VET
Para i de 1 até 10 faça
leia VET[i];
Fim-para;
// Leitura do valor a ser pesquisado (busca) 
leia (busca);
PESQUISA BINÁRIA - ALGORITMO // ALGORITMO 
inicio ← 1
fim ← 10
achou ← falso
enquanto ((inicio <= fim) E não achou) faça
meio ← (início + fim) DIV 2
SE VET[meio] = busca ENTÃO
achou ← verdadeiro
SENÃO
Se VET[meio] > busca
Então fim ← meio - 1
Senão início ← meio + 1
fim-se
FIM-SE
Fim-enquanto
ALGORITMOS-II TEMA_09 4 MANUEL
// Resultados da Pesquisa Binária 
SE achou ENTÃO
Início
imprima ('Valor encontrado...');
imprima ('Posição: ',meio);
Fim
SENÃO
imprima ('Valor não encontrado...');
FIM-SE
FIM-ALGORITMO
N  N/2  N/4  N/8  N/16... iteraçãok4321k
2
N
K
== ,..,,,,
N
2sComparaçõedeMaximoNúmero log=
PESQUISA BINÁRIA
Número máximo de comparações em função da quantidade de
dados (N)
O algoritmo para quando 1
2
N
K
=
K2N = N2k log=
Exemplos  Calcular o número máximo de iterações
para N = 50, 300,1000 (ENADE)
66,5log502 ≅=
1096,9log10002 ≅=
922,8log3002 ≅=
3225 = 6426 =
51229 = 1024210 =
25628 = 51229 =
PESQUISA BINÁRIA
COMPLEXIDADE DA PESQUISA BINÁRIA
N = 16
24
23
22
21
20
NsComparaçõedeMaximoNúmero 2log=
!log scomparaçõe4
16
2 = 162
4
=
Carpe Diem 
ALGORITMOS-II TEMA_09 5 MANUEL