Aula03-PesquisaBinaria

Prévia do material em texto

1
Classificação e Pesquisa
Prof. Antonio Felicio Netto
Pesquisa Binária
2
Estrutura de Dados
- Uma estrutura de dados é um meio para armazenar e organizar 
dados com o objetivo de facilitar o acesso e as modificações. 
- Nenhuma estrutura de dados funciona bem para todos os 
propósitos. Assim, é importante conhecer os pontos fortes e as 
limitações de várias delas.
- Estruturas de dados e algoritmos são temas fundamentais da 
ciência da computação, sendo utilizados nas mais diversas áreas 
do conhecimento e com os mais diferentes propósitos de 
aplicação.
3
Estrutura de Dados - Divisão
- Homogêneas : vetores e matrizes
- Heterogêneas: registros
4
Estrutura de Dados Homogêneas
- São conjuntos de dados formados pelo mesmo tipo de dado 
primitivo;
- Quando uma determinada Estrutura de Dados for composta de 
variáveis com o mesmo tipo primitivo, temos um conjunto 
homogêneo de dados;
- As variáveis compostas homogêneas correspondem a 
posições de memória, identificadas por um mesmo nome, 
individualizadas por índices e cujo conteúdo é de mesmo tipo;
- Exemplo : O conjunto de 10 notas dos alunos de uma disciplina 
pode constituir uma variável composta. A este conjunto associa-
se o identificador NOTA que passará a identificar não uma única 
posição de memória, mas 10;
5
Estrutura de Dados Heterogêneas
- Também conhecido como Registros;
- Diferentemente das estruturas de dados homogêneas, os 
registros permitem guardar dados de tipos variados;
- O registro permite que informações relacionadas mantenham-se 
juntas. A declaração de um registro define um tipo de dado, ou 
seja, informa ao computador o número de bytes que será
necessário reservar para uma variável que venha a ser declarada 
como sendo desse tipo;
- Exemplo : O conjunto de 10 alunos com seus dados de 
identificação (nome e RA) e a nota em uma disciplina pode 
constituir uma variável composta. A este conjunto associa-se um 
registro que passará a identificar a toda a estrutura alocada e não 
somente a um tipo primitivo;
6
Principais operações realizadas em Estruturas de Dados
- BUSCA: Dado um valor X, procura na estrutura pelo valor 
fornecido e retorna sua posição, caso encontrado;
- INSERÇÃO: Dado um novo elemento , insere-o na posição 
adequada;
- REMOÇÃO: Dado um elemento X procura na estrutura pelo 
valor fornecido e o remove, sem que haja prejuízo à estrutura;
- ALTERAÇÃO: Dado um elemento X e um novo valor Y procura 
na estrutura pelo valor X fornecido e, se encontrado, altera-o para 
o valor Y fornecido. 
7
Lista Linear
- Lista linear é a estrutura que permite representar um conjunto 
de dados afins de forma a preservar a relação de ordem linear de 
seus elementos.
-Uma lista linear, ou tabela, é um conjunto de n >= 0 nós 
L[i], L[2], ..., L[n] tais que suas propriedades estruturais decorrem, 
unicamente, da posição relativa dos nós dentro da sequência 
linear;
- Se n>0, L[1] é o primeiro nó
Para 1 < k <= n, o nó L[k] é precedido por L[k-1].
- Exemplo: Pessoas esperando ônibus; Letras de uma palavra; 
Pilhas de provas; 
8
Tipos de Armazenamento
- O tipo de armazenamento de uma lista linear pode ser 
classificado de acordo com a posição relativa na memória de dois 
nós consecutivos da lista:
1.Alocação sequencial de memória;
2.Alocação encadeada ou dinâmica.
- A escolha do tipo depende das operações que se desejam 
realizar.
9
Alocação Sequencial
- A maneira mais simples de se manter uma lista linear na 
memória do computador é colocar seus nós em posições 
contíguas (VETORES);
- Considere um vetor de registros onde cada registro possui 
campos que armazenam as características distintas dos 
elementos da lista;
- Cada nó da lista possui, geralmente, um campo identificador 
distinto chamado chave. 
- Os nós podem ou não estarem ordenados pelo campo chave.
10
Alocação Sequencial
11
Alocação Dinâmica
- A alocação dinâmica é o processo que aloca memória em tempo 
de execução. Ela é utilizada quando não se sabe ao certo quanto 
de memória será necessário para o armazenamento das 
informações, podendo ser determinadas em tempo de execução 
conforme a necessidade do programa;
- Considere uma lista de registros de tamanho n onde cada 
registro possui campos que armazenam as características 
distintas dos elementos da lista;
- A lista é constituída por nós ligados por meio de ponteiros;
- Cada nó da lista possui, geralmente, um campo identificador 
distinto chamado chave. 
- Os nós podem ou não estarem ordenados pelo campo chave.
12
Alocação Dinâmica
13
Pesquisas de Dados
- Na computação são inúmeras as situações em que é necessária 
a realização de busca por uma informação em alguma estrutura 
de dados; 
- A eficiência da busca vai depender exatamente da organização 
dos dados na estrutura em si;
14
Importância de pesquisar
- A busca é necessária em situações como:
Inserção de um novo dado: é necessária uma busca para 
verificar se o elemento a ser inserido já não existe na estrutura;
Alteração de um dado: é necessário buscar o dado para que o 
mesmo sofra a atualização;
Exclusão de um dado: o dado a ser excluído deve ser buscado 
para que possa deixar de fazer parte da estrutura, caso seja 
encontrado.
15
Importância do estudo dos algoritmos de busca
- Como existem outras operações dependentes do resultado de 
uma pesquisa a sua efetivação, há uma dependência de seu 
tempo para a agilidade das rotinas;
- Sem o estudos das técnicas de recuperação da informação não 
podemos evoluir a velocidade dos algoritmos necessitando 
diretamente da velocidade de processamento dos equipamentos 
(hardware).
16
Exemplo da importância
- Lista telefônica:
-Busca por um número a partir de um nome;
- Busca por um número a partir da área de atuação (Páginas 
amarelas); 
- Busca de um nome a partir de um número ( tem como?) 
- Nesse caso, a ordenação dos dados é importante para a agilizar 
o processo de pesquisa;
17
Métodos clássicos de busca
- Pesquisa de dados Linear (Sequencial);
- Pesquisa de dados binária; 
18
Pesquisa sequencial
- Um problema comum na computação é determinar a posição de 
um elemento em um vetor, ou determinar que ele não está
presente;
- Quando se tem um vetor sem ordenação, é necessário o uso da 
busca linear, na qual todos os elementos são verificados, 
sequencialmente, até que se encontre o elemento procurado ou 
até que todo o vetor tenha sido percorrido;
19
Pesquisa sequencial: Graficamente
20
Pesquisa sequencial: Algoritmo
21
Análise da pesquisa sequencial
- A busca linear leva, no pior caso, tempo proporcional ao 
tamanho n do vetor;
C (n) = n
- No melhor caso, leva tempo constante (podemos dar sorte e o 
elemento procurado ser o primeiro);
C (n) = 1
- No caso médio dizemos então que a pesquisa será:
C (n) = (n+1)/2
- E uma pesquisa sem sucesso será:
C (n) = n+1
22
Análise da pesquisa sequencial
- A busca linear também pode ser aplicada num vetor ordenado. 
Seu algoritmo, neste caso, sofre algumas alterações para que 
haja um pouco mais de eficiência, aproveitando-se da ordenação 
dos dados.
- No caso do vetor ordenado, a busca linear pode ficar um pouco 
mais eficiente, pois a ordenação permite parar uma busca 
desnecessária. 
- Isso melhora o processamento, mas o algoritmo também tem 
complexidade O(N)
23
Análise da pesquisa sequencial
24
Pesquisa Binária
- É possível buscar algo em um vetor sem verificar todos os 
elementos? 
Se o vetor estiver ordenado pelo campo de busca, sim. 
- Quando se tem elementos de algum domínio ordenável, pode-
se realizar busca em tempo proporcional a log2N;
- O algoritmo de busca binária requer que os elementosdo vetor 
estejam ordenados de forma crescente e não permite a existência 
de elementos duplicados no vetor;
25
Analogia com a pesquisa na Lista Telefônica
- Ao invés de procurar linearmente página por página a partir da 
primeira, fazemos uma estimativa de onde o elemento procurado 
deve estar (de acordo com o nome da pessoa) e abrimos a lista 
naquela posição. 
- Se os nomes da página aberta estiverem após o nome 
procurado, descartamos as páginas localizadas após o nosso 
chute inicial e repetimos a busca no trecho entre a primeira 
página e o local da primeira estimativa.
26
Pesquisa Binária
- Quando não se tem informação sobre os dados do vetor, uma 
boa estimativa é pegar o elemento do meio do vetor, V [N/2]. Se o 
elemento procurado, x, estiver antes de V [N/2], repetimos a 
busca somente no vetor V [0] . . . V [N/2];
- O número de vezes que conseguimos dividir algo por 2 até
chegar em vetores de 1 elemento é log2N. Portanto, a busca 
binária leva tempo proporcional a log2N;
- Dessa maneira, a busca binária começa sempre pelo “meio” do 
vetor, eliminando um grupo de elementos;
27
Pesquisa Binária: Graficamente
28
Pesquisa Binária: Algoritmo iterativo
29
Pesquisa Binária : procurando o valor 50
30
Pesquisa Binária: Algoritmo recursivo
31
Exemplo de pesquisa binária recursiva
- Seja o vetor abaixo com N=20 elementos
Deseja-se encontrar a posição do elemento 80.
Na primeira chamada da função os valores são:
X = 80 ; l = 0 e r = 19
32
Exemplo de pesquisa binária recursiva
33
Exemplo de pesquisa binária recursiva
34
Exemplo de pesquisa binária recursiva
35
Exemplo de pesquisa binária recursiva
36
Exemplo de pesquisa binária recursiva
37
Exercício
1 – Elabore um algoritmo que realize o cadastro de 20 números 
inteiros em um vetor;
2 – Elabore um algoritmo que realize o cadastro de 20 números 
inteiros distintos em um vetor;
3 – Elabore um algoritmo que permita a pesquisa de forma 
sequencial em um vetor de nome Vet, onde o seu tamanho é
passado como parâmetro na função de pesquisa;
4 – Elabore um algoritmo que permita a pesquisa usando o 
método de pesquisa binária em um vetor de nome Vet, onde o 
seu tamanho é passado como parâmetro na função de pesquisa;