Capítulo 3 – Algoritmos de Pesquisa

1. Introdução

Um algoritmo de pesquisa tem a função de confirmar a existência (e em

alguns casos até a localização) de uma chave , dentro de um
conjunto de chaves qualquer.

2. A pesquisa sequencial

A pesquisa sequencial, sem sombra de dúvidas, é a forma mais simples

de realizar a pesquisa por uma chave , dentro de um vetor. O nome se
deve ao fato dos elementos do vetor serem “comparados” com a
chave na sequência em que aparecem organizados.

A pesquisa sequencial começa no elemento que está no início do vetor

e se encerra ao encontrar a chave ou após se passar por todos os
elementos. O Quadro 1 apresenta o pseudocódigo da função de
pesquisa sequencial.

int pesquisa(int k, int[] vetor) {

for(int i = 0; i<[Link]; i++) {
if (vetor[i] == k)
return i;
}//endfor
return -1;
}//endfuncao
Quadro 1: Algoritmo da Pesquisa Sequencial

A função da pesquisa sequencial recebe como entrada,

respectivamente, a chave e o vetor onde será consultada a
existência dessa chave. Na implementação do Quadro 1, o método
retorna o índice onde está guardado a chave dentro do vetor. Caso
se passe por todos os elementos do vetor e a chave não seja
encontrada, o laço interrompe sua execução e o método retorna o
valor -1 para representar uma situação de erro.

Uma análise superficial sobre as características do algoritmo da

pesquisa sequencial indicará que o tempo de execução do algoritmo é
descrito por uma função linear (visto que ele é composto por um laço
que depende do tamanho da entrada).
Entretanto, ao fazer a contagem de instruções da função de pesquisa,
o tempo de execução exato é descrito pela função ( ) . Essa
análise está apresentada no Quadro 21.

int pesquisa(int k, int[] vetor) { Total de Instruções

int i = 0;
while (i < [Link]) {
if (vetor[i] == k)
return i;
i++;
}//endwhile
return -1;
}//endfuncao Custo Total:
Quadro 2: Análise do Tempo de Execução da Pesquisa Sequencial

O método de pesquisa sequencial é bastante simples e largamente

ensinado durante cursos de programação. Entretanto, há alguma
melhoria que poderia ser implementada no método, de forma a deixa-
lo mais eficiente? Existe algum trecho do código que é poderia ser
excluído ou otimizado?

Vamos analisar cada parte do código: a inicialização da variável que

controlará o laço é essencial para determinar de onde começa a
busca; o teste que controla o laço é importante para o caso do
elemento não estar no vetor, pois evita “estourar” o limite superior dos
índices; o incremento do contador i também é importante para que se
possa mudar a posição que está sendo testada dentro do vetor; o teste
para verificar se o elemento da posição atual do contador é igual à
chave k é a base do algoritmo de pesquisa; por fim, os retornos
também não poderiam ser retirados.

Você consegue identificar qual trecho poderia ser editado para

melhorar a performance do algoritmo de pesquisa? Resposta: o teste
que controla o laço só é necessário por que não temos certeza se a
chave k se encontra ou não na sequência. Caso ela não faça parte da
sequência, o algoritmo nunca entraria na cláusula if dentro do laço. E,
dessa forma, o valor do contador aumentaria tanto que “estouraria” o
limite superior dos índices do vetor. Isso cria uma oportunidade de
otimização.

1
Na análise, considerou-se que as células em cinza executam em um segundo. Como só haverá um
retorno e, após o laço, não há outras instruções a serem executadas, independente do elemento ser
encontrado ou não, o custo total aumenta em um segundo. Além disso, lembre-se que, na análise
assintótica, deve-se sempre considerar o pior caso de execução dos algoritmos.
Se fosse possível garantir que a chave k está na sequência, não seria
necessário o teste condicional do laço. Mas, como podemos garantir
isso? Resposta: uma das variações do algoritmo da pesquisa sequencial
é a “pesquisa sequencial com sentinela2”, a qual consiste em incluir o
elemento que está se buscando no final da sequência3. Dessa forma,
com certeza a chave k será encontrada, em alguma posição do vetor.
Após encontrar a chave, testa-se se o que foi encontrado está na última
posição da sequência (indicando que o elemento não estava
originalmente na sequência) ou em uma posição anterior (indicando
que o elemento estava de fato na sequência). Essa variação do
algoritmo da pesquisa sequencial está apresentada no Quadro 3.

int pesquisa(int k, int[] vetor) { Total de Instruções

//inserindo o elemento no final do vetor
vetor[[Link] – 1] = k;
int i = 0;
while(vetor[i] != k)
i++;
//removendo o elemento do final do vetor
vetor[[Link] – 1] = 0;
if (i == [Link]-1)
return -1;
Else
return i;
}//endfuncao Custo total:
Quadro 3: Algoritmo da Pesquisa Sequencial com Sentinela

Como pode ser observado no Quadro 3, o tempo de execução do

algoritmo da pesquisa sequencial com sentinela é descrito pela função
. Considere um vetor com 1000 elementos, no pior caso, a
pesquisa sequencial leva 3002 instruções, enquanto a sua variação leva
2005 instruções.

Embora tanto o algoritmo da pesquisa sequencial como da pesquisa

sequencial com sentinela sejam ( ) (de ordem linear), o segundo é
mais eficiente. Entretanto, será que é possível uma variação ainda mais
eficiente? Um algoritmo de pesquisa que realize e busca em tempo
constante, por exemplo? Resposta: claro que é impossível desenvolver
um algoritmo que realize busca em tempo constante, entretanto, há
outra otimização da pesquisa sequencial que pode ser usada para
oferecer a algumas buscas específicas um custo ( ) (constante).

2
Também conhecida como “pesquisa sequencial com dummy”.
3
Quem usar essa variação tem de deixar a última posição do vetor livre para receber quaisquer valores.
Existe uma teoria, dentro da Ciência da Informação, que diz que, se
uma informação é necessária agora, há uma grande probabilidade,
desta mesma informação, ser necessária novamente, no futuro próximo.
Em outras palavras, se usamos o método de pesquisa para testar a
existência de uma chave, provavelmente, vamos precisar usar esse
método de novo, para consultar posição da mesma chave, em um
curto intervalo de tempo.

Com isso em mente, podemos tentar tornar o próximo acesso um pouco

mais eficiente. Como? Resposta: Simplesmente, quando o método
pesquisar for chamado e encontrar a chave dentro do vetor, o próprio
método reorganiza os elementos dentro do vetor, trocando a chave
procurada de posição com o primeiro elemento. Dessa forma, em uma
próxima busca, a chave será rapidamente encontrada, dado que ela
agora se situa no início do vetor (a segunda busca terá tempo
constante). Essa técnica de busca é chamada de pesquisa sequencial
com transposição.

O pseudocódigo dessa versão da pesquisa sequencial está

apresentado no Quadro 4.

int pesquisa(int k, int[] vetor) { Total de Instruções

int i = 0;
while (i < [Link]) {
if (vetor[i] == k) {
vetor[i] = vetor[0];
vetor[0] = k;
return 0;
}//endif
i++;
}//endwhile
return -1;
}//endfuncao Custo Total: ( )
Quadro 4: Análise do Tempo de Execução da Pesquisa Sequencial com Transposição

As linhas destacadas no Quadro 4 descrevem o processo de troca de

posições entre o elemento guardado no início do vetor e a chave que
se está buscando. Depois dessa troca, o método de pesquisa retorna o
valor 0, que corresponde a nova posição da chave k, dentro da
sequência.

O método de pesquisa sequencial com transposição tem tempo, no

pior caso, descrito pela função . Isso significa que ele é mais
ineficiente que a pesquisa sequencial comum. Então, qual a vantagem
de usá-lo? Resposta: A vantagem dessa técnica é apenas a
perspectiva de ter uma próxima consulta em tempo constante (mais
eficiente).

3. A pesquisa em lista ordenada

A pesquisa em uma lista ordenada é um caso particular, pois se pode

usar do conhecimento que a lista encontra-se ordenada para otimizar
as operação de busca.

A técnica mais simples é a pesquisa sequencial em lista ordenada.

Consiste apenas em uma variação considera que a pesquisa só pode
continuar acontecendo enquanto a comparação estiver sendo feita
com um elemento menor do que o que está sendo buscado. O Quadro
5 apresenta o pseudocódigo dessa variação.

int pesquisa(int k, int[] vetor) {

for(int i = 0; i<[Link]; i++) {
if (vetor[i] >= k){
if (vetor[i] == k)
return i;
else
return -1;
}//endif
}//endfor
return -1;
}//endfuncao
Quadro 5: Algoritmo da Pesquisa Sequencial em Lista Ordenada

O trecho que aparece destacado é a principal diferença entre essa

versão, do algoritmo da pesquisa sequencial, e a original. Se a busca
chegar a um elemento que seja maior que a chave que se está
buscando, não adianta continuar a iteração, visto que a lista está
ordenada. Assim, se a condição for verdadeira, isso se deu por um
desses dois motivos: (1) a chave k foi encontrada na posição i; ou, (2) a
posição que o contador i está marcando contém um elemento maior
que a chave k. Esses dois casos estabelecem o fim do laço, por isso, no
final, confirma-se por qual razão se entrou no if, para então definir qual
o retorno.

Embora a versão da pesquisa sequencial apresentada no Quadro 5

também pertença a classe dos algoritmos representados por funções
lineares, na prática, a otimização causada pelo trecho destacado, faz
com que o tempo médio de pesquisa passe a ser ( ). Isso significa que
há algum ganho decorrente dessa mudança.
Entretanto, existe outra estratégia utilizada para realizar buscas em
sequências ordenadas que é tremendamente mais eficiente: a busca
binária.

Os métodos de pesquisa sequencial iniciam a procura pelo elemento

de uma ponta do vetor (normalmente à ponta esquerda) e continuam
sequencialmente na outra direção (normalmente, em direção à ponta
direita), conforme ilustrado abaixo4.

k=2 k=2 k=2 k=2 k=2

i=0 i=1 i=2 i=3 i=5
↓ ↓ ↓ ↓ ↓
5 3 1 4 2 5 3 1 4 2 5 3 1 4 2 5 3 1 4 2 5 3 1 4 2
0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4

O processo descrito no exemplo acima, também serve para descrever

a pesquisa sequencial em lista ordenada. Entretanto, no caso de listas
ordenadas, não é muito eficiente (nem inteligente) começar a pesquisa
pelo início do vetor.

A busca binária propõe começar o processo de busca pela posição do

meio do vetor. Dessa forma, a cada teste realizado, elimina-se metade
dos “candidatos” restantes. Considere, por exemplo, a sequência
ordenada abaixo:

10 20 30 40 50 60 70 80 90 99
0 1 2 3 4 5 6 7 8 9

Considere que estamos procurando pela chave “60”. O primeiro passo

do método de pesquisa binária é calcular o índice do elemento do
meio. Essa posição pode ser obtida calculando a média entre o
primeiro índice da sequência e o último índice da sequência. Na
sequência acima, a média resulta em 4,5.

A opção por arredondar para cima ou para baixo cabe ao

programador. Sugere-se apenas repetir essa mesma opção, seja por
arredondar para cima ou para baixo, em cada caso onde ocorrer essa
necessidade. Suponha-se que optamos por arredondar para baixo.

A busca binária propõe começar o processo de busca pela posição do

meio do vetor.

4
No exemplo, k representa a chave que se deseja consultar a posição e i representa a posição que se
está comparando com a chave k. No caso, quando o contador i alcança o valor 4, a busca se encerra,
pois se encontrou a chave k na sequência. Caso o i passasse dos limites dos índices do vetor, isso
significaria que a busca não foi bem sucedida.
 k=60
i=0 f=9 meio=4
↓
10 20 30 40 50 60 70 80 90 99
0 1 2 3 4 5 6 7 8 9

O elemento da posição 4 (o “50”) é comparado com a chave “60”. A

comparação vai identificar, obviamente, que o “50” não é o “60”. A
busca deve continuar na subsequência depois do “50”. Para isso,
atualiza-se o que o algoritmo considerará como início da sequência.
Visto que a chave que se está buscando é maior que o elemento que
está no meio, a consulta continuará do lado direito da sequência. A
variável i, que marca o início da sequência, é atualizada com o valor
meio+1 (4+1=5), para que a pesquisa continue a direita do meio.
Depois disso, calcula-se o novo índice do meio.

Nesta iteração, o índice que marca o início da sequência onde será

realizada a busca, agora, é “5”. A posição do meio será o resultado da
média entre o índice do primeiro elemento da sequência (5) e o índice
do último elemento da sequência (9). A média resulta em 7. Isso significa
que a posição 7 corresponde ao meio da sequência onde está sendo
feita a busca, agora5.

k=60
i=5 f=9
meio=7
↓
10 20 30 40 50 60 70 80 90 99
0 1 2 3 4 5 6 7 8 9

O elemento da posição 7 (o “80”) é comparado com a chave que se

está buscando (o “60”). Novamente, a comparação vai identificar que
o elemento da posição meio não é o que está sendo buscado. Além
disso, a comparação vai identificar que o elemento da posição 7 é
maior que a chave do meio. Dessa forma, o elemento que se está
buscando deve estar à esquerda do meio, na sequência. Nesse caso,
ao invés de atualizar a variável que guarda o início da sequência,
atualiza-se a variável que guarda o final da sequência. Nesse caso, a
variável f vai receber o valor meio-1, isto é, “6”. Depois disso, calcula-se
o novo índice do meio. A busca vai continuar considerando esse novo
espaço da sequência.

5
Nas próximas figuras, a parte do vetor que aparece com as arestas destacadas em negrito corresponde
à área que estará sendo considerada para realizar a pesquisa
Nesta iteração, o índice que marca o início da sequência é o mesmo
da iteração anterior, mas o índice do final mudou sendo agora “6”. Ao
calcular a nova posição do meio, obtém-se o valor 5,5 ( ). Esse valor,
arredondado para baixo, resultará novamente na marcação da
posição “5”, como meio.

k=60
i=5 f=6 meio=5
↓
10 20 30 40 50 60 70 80 90 99
0 1 2 3 4 5 6 7 8 9

Agora, entretanto, a comparação com a chave “60” indicará que o

elemento foi encontrado e o valor da variável meio é usado como
retorno do método de pesquisa. Caso o elemento não tivesse sido
encontrado, continua-se atualizando os valores das variáveis i e f, até
que a chave seja identificada ou até que o valor da variável que
marca o início da sequência seja superior ao da variável que marca o
fim6.

Como podemos começar a implementar esse método? A pesquisa

binária pode ser codificada de forma iterativa ou de forma recursiva.
Para ilustrar sua implementação, vamos, a princípio, nos ater a versão
iterativa do método.

Podemos começar apenas criando as variáveis que serão usadas

durante o processo de busca. Essa parte inicial da função está ilustrada
no Quadro 6.

int pesquisa(int k, int[] vetor) {

int i = 0;
int f = [Link]-1;

//continua

}//endfuncao
Quadro 6: Trecho do Algoritmo da Pesquisa Binária – parte 1

O processo de busca acontece dentro de um laço. Quando esse laço

termina? O laço termina quando a busca foi mal sucedida7. Como
comentado anteriormente, a condição para a busca parar é, depois

6
Essa situação identifica que a busca não foi bem sucedida e o elemento não foi encontrado, dentro da
sequência.
7
Caso a busca seja bem sucedida, o retorno do resultado acontecerá dentro do laço.
de consecutivas atualizações dos marcadores i e f, o valor da variável
i passar a ser maior que o da variável f8.

int pesquisa(int k, int[] vetor) {

int i = 0;
int f = [Link]-1;
while (e <= f) {

//continua

}//endwhile
return -1;
}//endfuncao
Quadro 7: Trecho do Algoritmo da Pesquisa Binária – parte 2

Quando a condição de parada do laço for alcançada (ou seja, i

passar a ser maior que o da variável f), significa que a busca não foi
bem sucedida. Nesse caso, o método retorna -1 para representar que o
elemento não foi encontrado.

Dentro do bloco do while, a primeira coisa que acontece é calcular o

índice do meio, utilizando a média das variáveis que guardam o índice
inicial (i) e final (f) da sequência.

Em seguida, compara-se o elemento que está nessa posição do meio

com a chave que está sendo pesquisada. Caso seja identificado que os
dois são iguais, retorna-se, no nosso caso, a posição do elemento
(meio).

int pesquisa(int k, int[] vetor) {

int i = 0;
int f = [Link]-1;
while (e <= f) {
int meio = (i+f)/2;

if (vetor[meio] == k)
return meio;

//continua

}//endwhile
return -1;
}//endfuncao
Quadro 8: Trecho do Algoritmo da Pesquisa Binária – parte 3

Essa é a condição de parada, pois, quando i passa do valor de f, é como se eu estivesse dizendo que
8

o início do vetor vem depois do final. Não faz muito sentido não é? Por essa razão, isso encerra o
processo de busca.
Caso o elemento do meio não seja igual à chave que se está
buscando, as opções que restam é a chave ser maior ou menor que o
elemento do meio. Agora, é importante identificar qual desses dois
casos é o correto, pois isso determinará se a pesquisa continuará do
lado esquerdo ou do lado direito da sequência. Antes da próxima
iteração, com base no resultado dessa comparação, a variável que
guarda o início (i) ou a que guarda o final da sequência (f) será
atualizada, conforme descrito anteriormente.

int pesquisa(int k, int[] vetor) {

int i = 0;
int f = [Link]-1;
while (e <= f) {

int meio = (i+f)/2;

if (vetor[meio] == k)
return meio;
else if (vetor[meio] < k)
i = meio+1;
else
f = meio-1;

}//endwhile
return -1;
}//endfuncao
Quadro 9: Algoritmo da Pesquisa Binária – código completo

A função da pesquisa binária é o método mais eficiente de busca,

entretanto, só pode ser usada em sequências ordenadas. O custo desse
algoritmo, no pior caso, é ( ).

4. Exercícios de Fixação

1. A pesquisa sequencial com transposição assume que, após realizar

uma busca bem sucedida, é interessante jogar o elemento encontrado
para o início do vetor. Entretanto, isso só se torna, de fato, interessante
se a próxima busca realiza for pelo mesmo elemento que foi procurado
da última vez que o método de busca foi chamado. Uma forma de
melhorar isso é deslocar todos os elementos da sequência para a direita
(transposição da sequência), ao invés de trocar de lugar apenas o
elemento procurado com o que está no início da sequência. Dessa
forma, codifique o método de pesquisa sequencial que realiza a
transposição dessa forma.
2. [FCC – 2018 – DPE - Programador] Considere que na Defensoria há
uma lista ordenada com o nome de 1000 cidadãos amazonenses.
Utilizando o método de pesquisa binária para localizar o nome de um
destes cidadãos, serão necessárias, no máximo (0,25):

a) 1000 comparações.
b) 10 comparações.
c) 500 comparações.
d) 200 comparações.
e) 5 comparações.

3. A pesquisa binária pode codificada de forma iterativa ou recursiva. O

código apresentado nesse capítulo é a versão iterativa. Dessa forma,
codifique a versão recursiva do método da pesquisa binária.

4. As técnicas especiais de pesquisa, algumas vezes, podem ser

combinadas, a fim de alcançar as vantagens pretendidas pelas
técnicas. Com isso em mente, responda:

a) É possível desenvolver um método de pesquisa binária com

transposição? Explique sua resposta.
b) É possível desenvolver um método de pesquisa com sentinela que
também usa transposição? Explique sua resposta.
c) É possível desenvolver uma pesquisa sequencial ordenada com
sentinela? Explique sua resposta.