Algoritmos1_Aula18-BuscaVetor

Prévia do material em texto

Busca em vetor
Algoritmos I
Prof. Thiago Meirelles Ventura
UFMT – IC – 2013/1
Introdução
O vetor é uma forma de armazenar valores
É de grande importância localizar determinados elementos dentro de um vetor
Por isso existem as buscas em vetores
Busca linear simples
Compara o elemento com cada item do vetor até encontrar o respectivo item
Busca linear simples
56
-34
1345
0
-371
0
Busca linear simples
56
-34
1345
0
-371
0
Busca linear simples
56
-34
1345
0
-371
0
Busca linear simples
56
-34
1345
0
-371
0
Busca linear simples
56
-34
1345
0
-371
0
Exercício 1
Faça um algoritmo que leia um numero inteiro n entre 1 e 100
Leia n valores reais em um vetor
Leia um valor x
Escreva na saída a primeira posição do vetor onde x aparece, ou zero caso não apareça.
Exercício 1
Resolver da maneira simples
Tentar otimizar 
Busca sequencial com sentinela
Está sendo feita uma comparação apenas para verificar se o laço chegou ao fim por encontrar o elemento ou por chegar ao fim do vetor.
E se tivermos certeza que o elemento sempre será encontrado?
Como podemos fazer isso?
Podemos inserir o elemento a ser encontrado no final do vetor (sentinela)
Busca binária
E se o vetor possuir milhões de elementos?
Quanto tempo levará a busca?
Busca binária
A maneiras mais eficazes de efetuar as buscas.
Uma delas é aproveitar da estratégia 
"dividir para conquistar”
A busca binária utiliza essa estratégia
Busca binária
Requisito:
O vetor deve estar ordenado
Procedimento:
O elemento buscado é comparado ao elemento do meio do vetor
Se igual, encontrou o elemento desejado
Se menor, busca-se na metade inferior do vetor
Se maior, busca-se na metade superior do vetor
Busca binária
Busca-se por 142
-147
-34
5
98
142
0
32
99
964
Busca binária
Busca-se por 142
-147
-34
5
98
142
0
32
99
964
Busca binária
Busca-se por 142
-147
-34
5
98
142
0
32
99
964
Busca binária
Busca-se por 142
-147
-34
5
98
142
0
32
99
964
Busca binária
Busca-se por 142
-147
-34
5
98
142
0
32
99
964
Busca binária
Busca-se por 142
-147
-34
5
98
142
0
32
99
964
Busca binária
Busca-se por 142
-147
-34
5
98
142
0
32
99
964
Exercício 2
Faça um algoritmo que leia um numero inteiro n entre 1 e 100
Leia n valores reais em um vetor
Assegura-se que o vetor será preenchido de maneira ordenada de forma crescente
Leia um valor x e escreva na saída a posição no vetor onde x aparece, ou zero caso não apareça
Utilize a busca binária.
Exercício 3
Faça um algoritmo que leia um vetor de até 500 elementos
Diga se ele está ordenado de forma ascendente e se os valores são todos distintos entre si
Em caso positivo, peça que ele digite ainda um valor x e diga em que posição do vetor ele aparece, utilizando uma técnica que tire vantagem da característica ordenada do vetor.