Algoritmos e Estrutura de Dados (Aula 5)

Prévia do material em texto

Algoritmos e 
Estrutura de Dados
Profa. Amanda Sutter
asutter@anhanguera.com
Outubro/2015
Última aula....
• Revisão/Aula de Vetores e Matrizes no laboratório
Pesquisa Sequencial e 
Pesquisa Binária
Pesquisa em Vetores (Arrays)
• Normalmente precisamos verificar se um determinado
dado existe em alguma posição de um vetor, ou se está
ausente.
• Para isso usamos algoritmos de busca, sendo os mais
comuns:
• Pesquisa sequencial
• Pesquisa binária
Pesquisa Sequencial em Arrays
• Na pesquisa sequencial, buscamos um valor dentro de
um array comparando-o com cada valor presente em
cada posição, seguindo a sequencia das posições do
vetor, da primeira até a última.
VET: vetor [1..3] de inteiro
NUM, POSICAO: inteiro
//entrar com valor a pesquisar
ESCREVAL(“Digite um número para pesquisar no array:”)
LEIA(NUM)
POSICAO <- 1
//pesquisar no array
ENQUANTO (POSICAO < 3) e (VET[POSICAO] <> NUM) FACA
POSICAO <- POSICAO + 1
FIMENQUANTO
SE VET[POSICAO]=NUM ENTAO
ESCREVAL(“Número encontrado na posição”, POSICAO)
SENAO
ESCREVAL(“Número não encontrado no array”)
FIMSE
Pesquisa Sequencial 
de Arrays
NUM (a pesquisar)
2
NUM = 2
POSICAO = 1
VET[POSICAO] = 4
POSICAO < 3? verdadeiro
VET[POSICAO] <> = NUM? verdadeiro
Pos 1
4
Pos 2
7
Pos 3
2
Array
Pesquisa Sequencial 
de Arrays
NUM (a pesquisar)
2
NUM = 2
POSICAO = 2
VET[POSICAO] = 7
POSICAO < 3? verdadeiro
VET[POSICAO] <> = NUM? verdadeiro
Pos 1
4
Pos 2
7
Pos 3
2
Array
Pesquisa Sequencial 
de Arrays
NUM (a pesquisar)
2
NUM = 2
POSICAO = 3
VET[POSICAO] = 2
POSICAO < 3? falso
VET[POSICAO] <> = NUM? falso
Pos 1
4
Pos 2
7
Pos 3
2
Array
Em C
#include<stdio.h>
int main()
{
int vet[3], num, posicao;
//preencher o array
for(posicao=0;posicao<3;posicao++)
{
printf("Digite um numero para inserir no array: ");
scanf("%d", &vet[posicao]);
}
//entrar com valor a pesquisar
printf("Digite um numero para pesquisar no array: ");
scanf("%d", &num);
posicao=0;
while((posicao < 3) && (vet[posicao] != num))
{
posicao=posicao+1;
}
if(vet[posicao]==num)
printf("Numero encontrado na posicao %d",posicao+1);
else
printf("Numero nao encontrado no array");
return 0;
}
Pesquisa binária em Arrays
• Criar vetor e ordená-lo:
3 8 6 4 2 1 9 7 3 5
Ordenar o vetor
1 2 3 3 4 5 6 7 8 9
Vetor ordenado e variáveis aux
1 2 3 3 4 5 6 7 8 9
7Número a ser pesquisado:
Variáveis auxiliares:
inicial
meio
final
encontrado
1
10
falso
1 2 3 3 4 5 6 7 8 9
7Número a ser pesquisado:
inicial meio
final
encontrado
1 10
falso
1 2 3 3 4 5 6 7 8 9
7Número a ser pesquisado:
inicial meio
final
encontrado
1 5 10
falso
1 2 3 3 4 5 6 7 8 9
7Número a ser pesquisado:
inicial meio
final
encontrado
6 5 10
falso
1 2 3 3 4 5 6 7 8 9
7Número a ser pesquisado:
inicial meio
final
encontrado
6 7 10
falso
1 2 3 3 4 5 6 7 8 9
7Número a ser pesquisado:
inicial meio
final
encontrado
6 7 10
verdadeiro
Pesquisa Binária - Algoritmo
inicial <- 1
final <- 10
dado_encontrado <- falso
enquanto (inicial <= final) e nao dado_encontrado faca
meio <- (inicial + final) DIV 2
se VET[meio] = busca então
dado_encontrado <- verdadeiro
fimse
se VET[meio] > busca então
final <- meio - 1
senão
inicial <- meio + 1
fimse
fimenquanto
algoritmo “Pesquisa Binária”
var
CONTADORA, CONTADORB: inteiro
NUM, AUX: inteiro
VET: vetor[1..10] de inteiro
BUSCA: inteiro
//variáveis para busca binária:
inicial, final, meio: inteiro
dado_encontrado: logico
inicio
//preencher o array criado
para CONTADORA de 1 ate 10 faca
escreval (“Digite um numero:”)
leia(NUM)
VET[CONTADORA] <- NUM
fimpara
//Ordenando o array criado
para CONTADORA de 1 ate 9 faca
para CONTADORB de CONTADORA + 1 ate 10 faca
se VET[CONTADORA] > VET[CONTADORB] então
AUX <- VET[CONTADORB]
VET[CONTADORB] <- VET[CONTADORA]
VET[CONTADORA] <- AUX
fimse
fimpara
fimpara
//Exibir o vetor ordenado
escreval (“Vetor ordenado. Preparado para busca binária:”)
para CONTADORA de 1 ate 10 faca
escreval (VET[CONTADORA])
fimpara
escreval ()
//Entrar com o valor a pesquisar no vetor
escreva (“Digite um valor para procurar no vetor:”)
leia (busca)
//Efetuar a pesquisa binária
inicial <- 1
final <- 10
dado_encontrado <- falso
enquanto (inicial <= final) e nao dado_encontrado faca
meio <- (inicial + final) DIV 2
se VET[meio] = busca então
dado_encontrado <- verdadeiro
fimse
se VET[meio] > busca então
final <- meio - 1
senão
inicial <- meio + 1
fimse
fimenquanto
//Exibir resultados da busca
se dado_encontrado = verdadeiro então
escreva (“Dado encontrado na posição”, meio)
senão
escreva (“Informaçao não encontrada no vetor”)
fimse
fimalgoritmo
f
A
t
Anhanguera Fama pitágoras
oD
VNIAIIELVI unic
o; ;> '
unime l IR0\
00
unopar