apostila

foi exigido no enunciado que fossem localizadas
todas as ocorreˆncias (este e´ outro problema). Enta˜o podemos modificar o co´digo para
a versa˜o apresentada na figura 10.16, simplesmente trocando-se o for por um while
que termina a execuc¸a˜o ta˜o logo o elemento seja encontrado (se for encontrado).
Este algoritmo e´ mais ra´pido, na me´dia, do que o anterior, embora o nu´mero de
comparac¸o˜es feitas possa ser a mesma no caso do elemento na˜o estar presente no
vetor. Mas, se dermos sorte, o elemento pode estar no in´ıcio do vetor e terminar bem
ra´pido. Na me´dia, espera-se que ele pare mais ou menos na metade do vetor, isto e´,
considerando-se uma distribuic¸a˜o uniforme dos elementos.
Mas como o lac¸o faz dois testes, no caso do elemento na˜o ser encontrado ele sera´
um pouco mais lento. Notem que o duplo teste no lac¸o e´ necessa´rio pois deve parar
ou porque achou o elemento ou porque o vetor terminou. Este segundo teste so´ vai
dar true uma u´nica vez, o que e´ um desped´ıcio.
Se pudesse haver garantia de que sempre o elemento procurado estivesse presente,
enta˜o poder´ıamos construir um teste simples, o que pode nos economizar alguma
computac¸a˜o. Esta garantia na˜o pode existir, certo? Mais ou menos. Digamos que o
programador deliberadamente coloque o elemento no vetor. Neste caso, ha´ a garantia
140 CAPI´TULO 10. ESTRUTURAS DE DADOS
function busca (x: real ; var v: vetor r ; n: integer) : integer ;
var i : integer ;
achou: boolean;
begin
achou:= false ;
i := 1;
while ( i <= n) and not achou do
begin
if v[ i ] = x then
achou:= true ;
i := i + 1;
end;
i f achou then
busca:= i − 1;
end;
Figura 10.16: Busca em vetores, segunda versa˜o.
de que ele esta´ presente. Mas algue´m pode perguntar: assim na˜o vale, se eu coloco
na˜o significa que ele ja´ estava presente, eu vou sempre encontrar o elemento “falso”.
Novamente, depende de onde o programador coloque o elemento. Digamos que ele
o coloque logo apo´s a u´ltima posic¸a˜o. Enta˜o, das duas uma: ou o elemento na˜o estava
no vetor original, e neste caso a busca pode terminar pois o elemento sera´ encontrado
apo´s a u´ltima posic¸a˜o; ou o elemento estava presente e sera´ encontrado antes daquele
que foi adicionado. Um teste final resolve a du´vida. Se for encontrado em posic¸a˜o
va´lida, e´ porque estava presente, sena˜o, na˜o estava.
Este elemento adicionado logo apo´s o final do vetor e´ denominado sentinela e seu
uso e´ ilustrado na versa˜o apresentada na figura 10.17.
function busca (x: real ; var v: vetor r ; n: integer) : integer ;
var i : integer ;
begin
v[n+1]:= x;
i:= 1;
while v[ i ] <> x do
i := i + 1;
i f i <= n then
busca:= i
else
busca:= 0;
end;
Figura 10.17: Busca em vetores com sentinela.
Apesar da melhoria, este algoritmo sempre faz um nu´mero de comparac¸o˜es que
pode atingir n no pior caso, isto e´, quando o elemento na˜o esta´ presente no vetor.
O caso o´timo e o caso me´dio na˜o mudam, embora o algoritmo, conforme explicado,
10.1. VETORES 141
fac¸a metade das comparac¸o˜es quando comparado com a versa˜o anterior. Desta forma
ele e´ apenas ligeiramente melhor do que o anterior.
Ainda, o programador deve garantir que a posic¸a˜o usada pelo sentinela nunca seja
usada como sendo um elemento va´lido, pois na˜o e´. O programador colocou o elemento
ali de maneira controlada, mas na˜o se trata de um elemento va´lido. Isto significa que
o nu´mero de elementos u´teis do vetor agora na˜o e´ mais max r (ou max i), mas sempre
um a menos. Normalmente se modifica a definic¸a˜o do tipo para prever este espac¸o
adicional para o programador.
const min r=0; max r=50;
min i=1; max i=10;
type vetor r= array [min r . .max r+1] of real ;
vetor i= array [ min i . . max i+1] of integer ;
E´ poss´ıvel tornar o algoritmo mais eficiente?
A resposta e´ sim2. Mas, para tornar a busca mais eficiente e´ preciso impor algumas
restric¸o˜es extra na forma como os dados sa˜o organizados em memo´ria..
Esta maneira consiste em considerar que os dados esta˜o de alguma forma respei-
tando uma ordem lexicogra´fica em memo´ria. Por exemplo, se forem nomes, esta˜o
em ordem alfabe´tica. Se forem nu´meros, esta˜o em ordem crescente (ou descrescente).
Porque isto e´ necessa´rio? Pois pode-se explorar a informac¸a˜o de ordenac¸a˜o para tornar
o me´todo mais eficiente.
No caso, podemos modificar a soluc¸a˜o anterior para que o algoritmo termine a
busca sempre que encontrar um elemento que ja´ e´ maior do que aquele que se esta´
procurando, pois o vetor esta´ ordenado. O programa da figura 10.18 foi implementado
com esta ideia.
function busca (x: real ; var v: vetor r ; n: integer) : integer ;
var i : integer ;
begin
v[n+1]:= x;
i:= 1;
while v[ i ] < x do
i := i + 1;
i f (v[ i ] = x) and ( i <= n) then
busca:= i
else
busca:= 0;
end;
Figura 10.18: Busca em vetores ordenados.
Apesar de termos explorado uma propriedade adicional que faz com que no caso
2Em disciplinas avanc¸adas de algoritmos se estudam me´todos bastante eficientes para este pro-
blema. No nosso caso veremos apenas um deles.
142 CAPI´TULO 10. ESTRUTURAS DE DADOS
me´dio a busca seja mais eficiente, no pior caso, aquele em que o elemento procurado
na˜o pertence ao vetor, ainda temos um algoritmo que faz tantas comparac¸o˜es quanto
o tamanho do vetor. E´ poss´ıvel fazer melhor? A resposta novamente e´ sim.
Como exemplo, considere o problema de se encontrar um verbete no diciona´rio.
Sabemos que estes verbetes se encontram em ordem alfabe´tica. Por este motivo,
ningue´m em sa˜ conscieˆncia procura um nome em ordem sequencial desde o in´ıcio, a
menos que esteja procurando algo que comec¸a com a letra “A”.
Suponha que o verbete inicia com a letra “J”. Normalmente se abre o diciona´rio
mais ou menos no meio. Se o nome presente no in´ıco da pa´gina for “menor” lexico-
graficamente falando do que aquele que se busca, por exemplo, algo comec¸ando com
a letra “D”, enta˜o, pode-se tranquilamente rasgar o diciona´rio, eliminando-se tudo o
que esta´ antes do “D” e continuar o processo com o que restou.
Na segunda tentativa abre-se novamente mais ou menos na metade do que sobrou.
Suponha que ca´ımos na letra “M”. Como estamos procurando o “J”, pode-se sem
problemas rasgar novamente o diciona´rio eliminando-se tudo o que segue o “M”, ate´
o fim. Resta procurar “apenas” entre o “D” e o “M”.
Aplicando-se consistentemente este processo repetidas vezes, sempre teremos um
diciona´rio dividido mais ou menos por 2. Se ele tinha 500 pa´ginas no in´ıcio, na segunda
vez tera´ 250 e na terceira 125, na quarta algo pro´ximo de 70 pa´ginas. E assim por
diante. Por isto que costumamos localizar rapidamente verbetes em um diciona´rio.
O algoritmo mostrado na figura 10.20, denominado de busca bina´ria, implementa
esta ideia. Procura-se o elemento no meio do vetor. Se encontrou, enta˜o pode parar.
Se na˜o encontrou, basta verificar se o valor encontrado e´ maior ou menor do que o
procurado. Se for maior, joga-se a metade superior fora e trabalha-se apenas com
a metade inferior. Se for menor, joga-se fora a metade inferior e trabalha-se apenas
com a metade superior. Novamente procura-se na metade do que sobrou e assim por
diante, ate´ que se encontre o elemento ou ate´ que se determine que na˜o e´ mais poss´ıvel
encontra´-lo.
Vamos agora comparar estas u´ltimas quatro verso˜es para o algoritmo de busca.
A tabela 10.19 resume o nu´mero de comparac¸o˜es feitas para diversos tamanhos de
entrada, sempre analisando o pior caso. O caso me´dio exige um pouco mais de cui-
dado para se calcular e na˜o sera´ estudado aqui. O caso o´timo e´ sempre uma u´nica
comparac¸a˜o para os casos: o algoritmo acha o elemento na primeira tentativa.
Versa˜o n = 10 n = 102 n = 104 n = 108
Busca simples (fig. 10.16) 20 200 20000 200000000
Busca com sentinela (fig. 10.17) 10 100 10000 100000000
Busca em vetor ordenado (fig.