02 - Pesquisa Sequencial e Binaria

Prévia do material em texto

[.·.]i Professor Lima
Ciências da Computação, 
Sistema de Informação e 
Tecnólogo em Analise e 
Desenvolvimento de 
Sistemas
Professor MSc Ivair Lima
Pesquisa, Ordenação e Técnicas de Armazenamento
4
[.·.]
Aula de Apresentação
2019
Lorem ipsum dolor sit 
amet, consectetur adip
isicing
68% Lorem Vitae
✓Apresentação
✓Conteúdos
✓Avaliações
✓Faltas
✓Mercado de TI
✓Mercado Acadêmico
www.professorlima.com/fmu
Pesquisa, Ordenação e Técnicas de Armazenamento
01 - Pesquisa Sequencial e Binaria
02 - Insertion Sort e Selection Sort
03 - Bubble Sort
01
02
7
[.·.]
Pesquisa 
Sequencial
Binaria
8
[.·.]
Pesquisa
Normalmente precisamos verificar se um determinado dado (elemento) existe em alguma posição
de um vetor (array), ou se está ausente.
Para isso usamos algoritmos de busca, sendo os mais comuns:
Pesquisa Sequencial
Pesquisa Binária
9
[.·.]
10
[.·.]
Pesquisa Sequencial
O modelo de pesquisa sequencial é, normalmente, usado para determinar a existência ou não de
um valor numa sequência (vetor) e, em caso afirmativo, determinar a sua posição na sequência.
Definição
11
[.·.]
Simulando
1 5 843 9 10 672
Pesquisa sequencial: Busca um valor (posição) dentro de vetor comparando-o com cada valor presente em cada posição,
seguindo a sequência das posições do vetor, da primeira até a última.
2 3 541 7 8 1096
2 3 541 7 8 1096
2 3 541 7 8 1096
Valor = 7
Posição = 6
12
[.·.]
◼ Pesquisa Seqüencial (PS)
❑ Forma mais simples de realizar pesquisas.
❑ Metodologia: Percorre o vetor, elemento por elemento,
verificando se o elemento desejado está presente no vetor.
Pergunta: Como verificar se o elemento 81 está presente no vetor acima?
Pergunta: Quantas comparações são necessárias para achar o elemento 81?
21 5 21114 98 46 245389 1 15 6162 70 25 188169
Pesquisa sobre Vetores
13
[.·.]
❑ Extremamente simples o algoritmo;
❑ Pode ser muito ineficiente quando o conjunto de
dados é muito grande.
Características
14
[.·.]
Desempenho 
Computacional
✓Pior Caso: é quando é necessário realizar n comparações (onde n é o número 
de elementos)
✓Melhor Caso: é quando é necessário realizar somente uma comparação
Qual o cenário de pior caso possível ?
Qual o cenário de melhor caso possível ?
✓Caso Médio: é quando é necessário realizar cerca de n/2 comparações.
Qual o cenário de caso médio possível ?
15
[.·.]
16
[.·.]
Pesquisa Binaria
Uma forma de acelerar (otimizar) a pesquisa de um elemento, numa sequência ordenada, consiste
em utilizar uma estratégia de partição (divisão) da sequencia em duas metades, para diminuir o
numero de elementos a analisar. A pesquisa começa por selecionar o elemento central da
sequencia e compara-o como valor procurado. Se o elemento escolhido for menor, então podemos
excluir a primeira metade a sequencia e analisamos apenas a segunda metade. Caso contrario,
podemos excluir a segunda metade da sequencia e analisamos apenas a primeira metade.
Definição
17
[.·.]
Simulando
1 5 843 9 2 672
2 2 431 6 7 985
Valor a ser pesquisado 
Ordenar o Vetor
7
Variáveis Auxiliares: 1Posição Inicial Meio Posição Final 10
Encontrado Falso
18
[.·.]
Simulando
2 2 431 6 7 985
Variáveis Auxiliares: 1
Posição Central = Posição Inicial + Posição Final / 2
Posição Central Posição Final5 10
Encontrado False
Valor a ser pesquisado 7
Valor a ser pesquisado 7
1º Passo
Posição Inicial
Comparado com a Conteúdo Posição Central 5
Int pMeio = 0 + 10 / 2 
pMeio = 5
19
[.·.]
Simulando
2 2 431 6 7 985
6Alterado a Posição Inicial Posição Central Posição Final5 10
2º Passo
Posição Central > Valor Pesquisado
Int pMeio = 6 + 10 / 2 
pMeio = 8
2 2 431 6 7 985
6Alterado a Posição Inicial Posição Central Posição Final5 10
3º Passo
Posição Central = Valor Pesquisado
Encontrado True
Valor a ser pesquisado 7
20
[.·.]
Pesquisa Binária (PB)
Forma mais eficiente de realizar pesquisas em relação ao 
método de PS.
Metodologia:
Consiste em comparar alguns itens do vetor com o dado (chave 
alvo) que deseja-se encontrar.
Premissa: os dados contidos no vetor já estão ordenados 
segundo um critério.
21
[.·.]
Algorithm 
Binary Search
22
[.·.]
Passos do processo:
1) Checar onde está o posição central do vetor.
2) Comparar o elemento da posição central (EPC) com a elemento procurado (EP).
3) Caso não encontre o dado no passo 2, continuar a pesquisa da seguinte forma:
Caso EP<EPC realizar a pesquisa no sub-vetor a esquerda do EPC, partindo do passo 1.
Caso EP>EPC realizar a pesquisa no sub-vetor a direita do EPC, partindo do passo 1.
Caso EP=EPC, então a pesquisa para com sucesso, pois achou o dado desejado! 
Narrativa
Pesquisa Binária (PB)
Obrigado!
“Seja o que a sua mente pode conceber e 
acreditar, ela pode conseguir.”