Busca sequencial
• Consiste em percorrer um vetor à procura de um
certo elemento.
• O valor procurado deve ser confrontado com cada
elemento do vetor, e o insucesso da busca só será
considerado caso tenhamos percorrido todo o vetor
sem ter encontrado tal elemento.
• A busca termina ou quando o elemento é
encontrado ou quando todo o vetor for percorrido
sem sucesso.
Pesq
Pesquisa Sequencial
Iß1
Achaß.F.
i < =10
.e.
Acha = .F.
N
S
Pesq = Vet [ i ]
N
S
ißi+1
Acha ß .V.
Acha = .V.
N
Pesq, “ não
foi
localizado”
S
Pesq, “ foi
localizado
na posição
“, i
algoritmo "PESQSEQ"
// Função : Mostra a pesquisa sequencial em um vetor
var
VET: vetor [1..10] de inteiro
PESQ, I: inteiro
ACHA:logico
RESP:caractere
inicio
// Preenche o vetor
para i de 1 ate 10 faca
escreva("Digite o ", I,". valor: ")
leia(VET[I])
fimpara
RESP<-"S"
enquanto RESP="S" faca
escreva ("Informe o valor a ser procurado: ")
leia (PESQ)
I<- 1
ACHA<-Falso
enquanto (I<=10) e (nao ACHA) faca
se PESQ = VET[I] entao
ACHA<-verdadeiro
senao
I<-I+1
fimse
fimenquanto
se ACHA entao
escreval (PESQ, " foi localizado na posição ", I)
senao
escreval (PESQ, " não foi localizado")
fimse
escreval () //pula uma linha
escreval ("Deseja procurar outro valor? (s/n)")
leia(RESP)
fimenquanto
fimalgoritmo
Busca Binária
• Se precisarmos apenas procurar um elemento, num
vetor, uma única vez, é mais rápido fazer uma busca
sequencial do que realizar uma ordenação completa do
vetor; mas se precisarmos fazer repetidas buscas no
mesmo vetor, será melhor que ele esteja ordenado.
• Uma das vantagens de se ter um vetor ordenado é
que há algoritmos de busca que só funcionam com
vetores nesta situação e que são mais eficientes que os
algoritmos de busca seqüencial.
• A busca binária é um dos métodos mais eficientes para
se encontrar um elemento em um vetor ordenado.
Pesquisa Binária
Pesq
Comecoß1
Finalß10
Achaß.F.
Comeco <= Final
.E.
Acha=.F.
Meioß(Comeco+Final) div 2
Pesq=Vet[Meio]
Pesq<Vet[Meio]
ComecoßMeio
+1
Achaß.V.
FinalßMeio -1
Acha=.V.
Pesq, “ não
foi localizado”
Pesq, “ foi
localizado “,
Meio
algoritmo "PESQBIN"
// Função : Mostra a pesquisa BINÁRIA em um vetor ORDENADO
var
VET: vetor [1..10] de inteiro
PESQ, I, COMECO, FINAL, MEIO: inteiro
ACHA: logico
RESP: caractere
inicio
// Preenche o vetor ***dados ordenados****
para i de 1 ate 10 faca
escreva ("Digite o “ , I , ". valor: ")
leia (VET[I])
fimpara
RESP<-"S"
enquanto RESP="S" faca
escreva ("Informe o valor a ser procurado: ")
leia (PESQ) //elemento a ser procurado
COMECO<- 1
FINAL<-10
ACHA<-Falso
enquanto (COMECO<=FINAL) e (nao ACHA) faca
MEIO<-(COMECO + FINAL)\2 //DIVISÃO INTEIRA POR 2
se PESQ = VET[MEIO] entao
ACHA<-verdadeiro
senao
se PESQ < VET[MEIO] entao
FINAL<- MEIO-1
senao
COMECO<- MEIO+1
fimse
fimse
fimenquanto
se ACHA entao
escreval (PESQ, " foi localizado na posição ", MEIO)
senao
escreval (PESQ, " não foi localizado")
fimse
escreval () //pula uma linha
escreval ("Deseja procurar outro valor? (s/n)")
leia (RESP)
fimenquanto
fimalgoritmo