Algoritmos de Busca: Busca Sequencial e Busca Binária

Prévia do material em texto

4ºAula
Algoritmos de busca
Objetivos de aprendizagem
Ao término desta aula, vocês serão capazes de: 
•	 compreender como funciona o problema da busca;
•	 saber como funciona a busca sequencial;
•	 entender o funcionamento da busca binária.
Olá, 
Agora, vamos estudar os algoritmos de busca. Iremos ver 
que são dois algoritmos muito usados na informática: a Busca 
Sequencial (ou linear) ou a Busca Binária. Ambos têm suas 
condições de uso e mecanismos de funcionamento diferentes. 
Nesta aula, estudaremos também a implementação dos códigos.
Lembre-se de ler atentamente a aula e fazer as atividades. 
E se necessário, estaremos a sua disposição nas ferramentas 
disponibilizadas na sua área de aluno(a).
Bons estudos!
Estrutura de Dados I 30
1 - O problema da busca
2 - A busca linear (ou sequencial)
3 - Busca binária
1 - O problema da busca
Vamos começar falando do objetivo dos algoritmos 
que apresentaremos nesta aula: a busca de valores. De uma 
forma simples, podemos definir como procurar algum valor 
armazenado em um conjunto de dados - nesta aula, vamos 
implementar esse conjunto sendo um vetor de dados.
De uma forma mais elaborada, podemos definir o 
problema da busca da seguinte forma: dado um valor x, e um 
vetor de n posições, em que seus índices se concentram na 
faixa de 0 a n-1, devemos encontrar o índice k, que por sua 
vez, é o índice onde está localizado o valor x.
73 99 15 24 85 12 45 65 23 35
Dado esse enunciado, podemos definir a seguinte 
colocação: O problema só vai funcionar se n for maior que 
0, pois caso n seja 0, o vetor é vazio, não contendo nenhum 
elemento.
Assim, os nossos algoritmos vão procurar no vetor se o 
valor x existe, e caso exista, devolva o índice k referente a esse 
valor x.
Definido o problema, vamos fazer uma decisão: qual 
valor retornar se um valor x não estiver no vetor?
Podemos convencionar devolver o valor n do vetor. Ou 
seja, se o vetor tiver cinco posições, e se o dado pedido não 
for encontrado, a função retornará cinco. Mas, isso requer 
que o usuário saiba com antecedência qual é o número de 
posições do vetor, para verificar se o índice devolvido aponta 
para um valor válido ou não.
Outra ideia pode ser devolver -1, ao invés do valor n. 
Essa decisão fará o mesmo impacto, só que com um detalhe: 
o número -1 sempre é um valor inválido para um índice de um 
vetor, independente de quantas posições contenham o vetor.
Por padrão, vamos adotar a convenção de devolver -1. 
Porém, apresentaremos algoritmos similares, com outras 
propostas de retorno.
Definido esse problema, vamos apresentar o primeiro 
algoritmo de busca: a busca linear.
2 - A busca linear (ou sequencial)
A busca linear é uma das soluções mais simples que 
existem na computação. Basicamente, consiste em varrer o 
vetor do início ao fim (ou do fim até o início), parando o 
processo caso: (I) o valor desejado for encontrado ou (II) não 
existirem mais posições subsequentes no vetor.
Nós fazemos a busca linear em nosso cotidiano, sem que 
Seções de estudo
você saiba. Quando estamos em um prédio ou em uma rua, 
de posse do número do local que desejamos entrar, andamos 
pelo prédio ou pela rua até que o número da residência 
desejada seja encontrado.
Outra situação análoga à busca linear são as antigas fitas 
de áudio (as fitas cassetes). Quando a pessoa desejava escutar a 
música preferida, ela deveria avançar manualmente a execução 
da fita até chegar ao ponto da música desejada. Ao contrário 
dos CDs e dos dispositivos mais modernos, as fitas (e os discos 
de vinil) executavam as músicas de maneira sequencial.
Figura 1 - Fita cassete
Fonte: Disponível em: <https://upload.wikimedia.org/wikipedia/commons/f/f1/
Tdkc60cassette.jpg>. Acesso em: 23 mar. 2018.
A Busca Linear pode ser representada de várias 
formas. Assim, vamos apresentar nesta aula algumas formas 
equivalentes de se fazer a busca linear. A primeira delas adota 
o valor de retorno -1, caso o valor não seja encontrado no 
vetor. Para chegarmos a esse valor, o programa varre o vetor 
de trás para frente, da última posição até a primeira posição, 
verificando se o valor na posição atual do vetor é igual ao 
valor que desejamos procurar.
Figura 2 - Fluxograma de funcionamento da busca linear
Fonte: Disponível em: <https://commons.wikimedia.org/wiki/File:Busca_
sequencial.png>. Acesso em: 23 mar. 2018.
Se o valor for encontrado, devolve-se o índice que 
corresponde à posição do vetor onde o valor for encontrado 
(lembre-se que quando uma instrução return é executada, a 
função é encerrada automaticamente). Se o loop varrer todo 
o vetor e não encontrar nenhum valor, a função é encerrada, 
devolvendo o valor -1.
31
 A seguir, reproduzimos o código dessa função:
Podemos também varrer o vetor da primeira posição 
até a última posição. Neste caso, temos um loop while que 
faz esse percurso. Ele percorre o laço se duas condições 
forem satisfeitas. Se o contador k for menor que o número 
de posições n do vetor e se o valor correspondente do índice 
k do vetor não for igual ao valor desejado x. Se essas duas 
condições forem satisfeitas, uma nova iteração é executada, 
incrementando o índice k. 
Se o valor x for encontrado no vetor, o loop é 
interrompido e o índice k da posição com o valor desejado 
é retornado. Se o valor não for encontrado e o índice k for 
igual ao número de posições n do vetor, o loop é encerrado, 
devolvendo o valor k, que nessa situação, terá o número de 
posições n do vetor.
Assim, para verificarmos se o elemento foi encontrado, 
devemos testar se o índice devolvido pela função corresponde 
a um índice válido do vetor, ou seja, verificar se é menor que 
o valor n.
A seguir, reproduzimos a função:
Desse código, podemos fazer mais uma otimização caso 
o vetor seja ordenado. Se o vetor for ordenado na forma 
crescente, sabemos que se encontrarmos um valor no vetor 
maior de que nós procuramos, não temos mais chances de 
encontrar o valor desejado.
Assim, uma pequena adaptação é realizada. Ao invés de 
testarmos se o valor do vetor na posição k for igual ao valor 
que estamos procurando, testamos se o valor na posição atual 
no vetor for menor que o valor x. Se o valor for igual, o loop 
é interrompido, indicando que o dado foi encontrado. Se o 
valor passou a ser maior que o procurado, estaremos gastando 
recursos computacionais à toa no caso de um vetor ordenado. 
Assim, nesta situação, a busca também é interrompida.
Segue o código dessa variante:
Vale lembrar que nesta situação, o valor que será 
retornado pode ser um índice válido do vetor, mesmo que 
o valor não seja encontrado. Assim, precisamos testar após 
a busca se o valor retornado corresponde a um índice válido 
no vetor e se o valor na posição k do vetor é igual ao valor 
procurado.
Como já falamos na aula 04, todo e qualquer problema 
computacional que for implementado com um loop de 
repetição, pode ser implementado usando o artifício da 
recursividade. A próxima variante da busca sequencial que 
apresentamos é uma adaptação recursiva. 
Na primeira chamada, inserimos o valor procurado x, o 
número de elementos do vetor n e o próprio vetor. A cada 
chamada, verifica se x está na posição n-1 do vetor. Ou seja, se 
um vetor dado for de 5 elementos, ele vai procurar primeiro se 
o valor x está na posição 4 do vetor. Caso não seja encontrado, 
a função vai procurar nas posições 3, 2, …, até chegar ao 
valor 0. Se na posição desejada o valor x for encontrado, o 
valor n-1 é retornado, que corresponde ao índice da posição 
encontrada.
Se o valor não for encontrado, uma nova chamada é feita, 
com os parâmetros x, n-1 (no lugar de n) e o vetor de busca. 
Se o parâmetro n for 0, é o sinal que nada foi encontrado e a 
Estrutura de Dados I 32
função vai retornar -1, indicando essa situação.
Explicado o seu funcionamento, vamos ao código:
A busca sequencial é um algoritmo simples. Mas tem 
os seus problemas. O melhor caso é Ω(1), que ocorre se o 
elemento a ser encontrado estiver na primeira posição a ser 
lida. Porém,o pior caso é O(n), pois envolve toda a leitura do 
vetor caso o valor a ser encontrado esteja na última posição ou 
quando o valor não é encontrado no vetor.
Porém, caso o vetor tenha os seus valores ordenados, 
podemos usar outro algoritmo que tira vantagem dessa 
particularidade da entrada. Na próxima seção, veremos a 
busca binária.
3 - Busca binária
A Busca Binária é uma alternativa a Busca Sequencial 
para vetores que estejam ordenados (matematicamente 
falando, é um conjunto de valores onde um valor anterior é 
sempre menor ou igual que o valor subsequente, no caso de 
um vetor ordenado de forma crescente). Ela é projetada para 
não precisar varrer todo o vetor na execução, procurando 
apenas entre os valores próximos do valor a ser encontrado.
Ao contrário da busca sequencial, a lógica aplicada 
nesse algoritmo é um pouco mais complicada. Assim, vamos 
explicar como funciona antes de apresentarmos os códigos.
Suponha que há um vetor de 10 posições, com os 
seguintes valores:
5 10 15 20 25 30 35 40 45 50
Desejamos encontrar o valor 20 nesse vetor. Assim, 
vamos iniciar nosso processo de busca. Primeiramente, 
encontramos a posição média do vetor, somando os valores 
das extremidades da esquerda e da direita e dividindo por 2. 
No momento as extremidades são o valor -1 e 9. Fazendo as 
contas: ((-1)+9) / 2 = 4.
Com o índice médio em mãos, vamos ver se o valor 
procurado é menor ou maior que o valor da posição média do 
vetor. O valor 20 é menor que 25. Como o vetor é ordenado, 
sabemos que é inútil verificar posições cujos valores sabemos 
que são maiores que o valor que devemos procurar. Assim, 
descartamos as posições posteriores à posição média, e o 
nosso vetor com os elementos procurados passa a ter como 
limites os índices entre 0 a 4.
5 10 15 20 25 30 35 40 45 50
Calculamos novamente a posição média do vetor, 
calculando (0+4)/2 = 2. A posição mediana passa a ser 
o valor 15. Assim, vemos se o valor 20 é maior ou menor 
que 15. Como o valor 20 é maior, sabemos que procurar o 
valor nas posições anteriores ao valor 15 é algo inútil. Assim, 
descartamos os índices menores que 2. Nosso vetor passa a 
ter a sua faixa de índices restrita entre 2 a 4, em apenas duas 
iterações.
5 10 15 20 25 30 35 40 45 50
Novamente, verificamos o valor da posição média do 
vetor nesse instante, calculando (2+4)/2 = 3. Verificamos 
que o valor 20 é igual ao valor que desejamos procurar. A 
extremidade direita passa a ser o valor 20. Como sobrou 
apenas um valor no vetor, retornamos o índice da extremidade 
direita, que corresponde ao índice do valor que desejamos 
procurar.
5 10 15 20 25 30 35 40 45 50
Esse é a base da busca binária. Em suma, ela tem quatro 
instruções:
1. Calcule o índice da posição média do vetor, através 
da seguinte fórmula: (esquerda + direita) / 2.
2. Verifique se o valor procurado é maior ou menor em 
relação ao valor da posição média do vetor. Se for 
maior, adote o valor da posição média como a nova 
extremidade esquerda do vetor. Se for menor, adote 
o valor da posição média como a nova extremidade 
direita do vetor.
3. Prossiga os passos 1 e 2 enquanto que o número 
de elementos restantes do vetor for maior que 1 
(Verificado através da expressão esquerda < direita 
-1);
4. Se restar apenas 1 valor no vetor, retorne o índice da 
extremidade direita do vetor.
33
Figura 2 - Ilustração do funcionamento da Busca Binária
Fonte: Disponível em: <https://image.slidesharecdn.com/estruturadedados-aula12-pesquisadedadossequencialebinria-170203184523/95/estrutura-de-dados-aula-12-
pesquisa-de-dados-sequencial-e-binria-26-638.jpg?cb=1486148483>. Acesso em: 23 mai. 2018.
A busca binária divide o vetor em duas porções a cada 
interação e descarta a porção que tem certeza absoluta de que 
o valor não será encontrado. Assim, mesmo que o valor não 
esteja no vetor, não será necessária a leitura de todo o vetor 
para chegar a essa conclusão. A sua complexidade de tempo é 
O(log2n), que comprova que seu desempenho é muito melhor 
do que a busca binária. Observe o quadro comparativo:
Tabela 1 - Quadro comparativo de complexidade de 
tempo entre a busca binária e a busca sequencial
n O(n) O(log2n)
10 10 3,32*
100 100 6,64*
1000 1000 9,96*
10000 10000 13,28*
100000 100000 16,61*
Fonte: Acervo Pessoal
* valor aproximado
Agora que você está familiarizado com o mecanismo 
de funcionamento da busca binária, vamos apresentar dois 
códigos que realizam a busca binária. A primeira versão usa 
um loop de repetição para implementar a busca.
A segunda versão usa o mecanismo da recursividade para 
implementar essa solução. Para isso, são usadas duas funções. 
A função busca_binaria_rec é a função que devemos focar os 
nossos estudos, pois é ela que faz a implantação do algoritmo. 
Já a função busca_bin traduz os parâmetros das outras funções 
para um conjunto de parâmetros que seja entendido pela 
função busca_binaria_rec. Com isso, o usuário só precisará 
mudar o nome da função e não mudar os parâmetros para 
usar a função busca_binaria_rec.
As duas funções têm uma particularidade em comum: 
ambas retornam um valor da faixa de índices válida do vetor, 
que pode representar o valor procurado ou um valor próximo 
ao que desejamos procurar (caso não esteja no vetor). Assim, 
devemos certificar se o valor foi encontrado, verificando se 
corresponde com o valor que desejamos encontrar:
E com isso, finalizamos a nossa aula de hoje. Lembre-se 
de fazer as atividades e de ver os materiais adicionais indicados 
Estrutura de Dados I 34
no final desta aula. Na próxima aula, veremos os algoritmos 
de ordenação.
Retomando a aula
Chegamos	ao	final	da	Aula	04.	Vamos	retomar	o	que	
vimos?
1 - O Problema da Busca
Nessa seção, vimos a introdução aprofundada sobre o 
problema da busca. Esse problema consiste em um valor x, e 
um vetor de n posições, sendo que seus índices se concentram 
na faixa de 0 a n-1, sendo que o objetivo é encontrar o índice 
k, que por sua vez, é o índice onde está localizado o valor x.
2 - A Busca Linear (ou Sequencial)
Nessa seção, vimos que a Busca Linear é um algoritmo 
simples de busca, que envolve a comparação sequencial de 
todas as posições do vetor, até quando o valor desejado for 
encontrado ou quando todo o vetor for lido, e o valor desejado 
não for encontrado. Esse algoritmo pode ser implementado 
de diversas formas. Sua complexidade de tempo para o pior 
caso é O(n), pois envolve a leitura de todo o vetor de entrada.
3 - Busca Binária
Nessa seção, vimos que a Busca Binária é uma alternativa 
a Busca Sequencial para vetores que estejam ordenados. Ela é 
projetada para não precisar varrer todo o vetor na execução, 
procurando apenas entre os valores próximos do valor a 
ser encontrado. Consiste em dividir o vetor ao meio a cada 
interação, descartando o conjunto em que não se tem a chance 
de encontrar o valor desejado.
CORMEN, Thomas H.; et. al. Algoritmos: teoria e 
prática. Rio de Janeiro: Campus, 2012.
SZWARCFITER, Jayme Luiz; MARKENZON, Lilian. 
Estruturas de dados e seus algoritmos. 2. ed. Rio de Janeiro: LTC, 
1994.
Vale	a	pena ler
FEOFILOFF, Paulo. Busca em vetor ordenado. USP, 
Vale	a	pena assistir
Vale a pena
2016. Disponível em: <https://www.ime.usp.br/~pf/
algoritmos/aulas/bubi.html>. Acesso em: 23 mai. 2018.
FEOFILOFF, Paulo. Busca Binária. USP, 2016. 
Disponível em: <https://www.ime.usp.br/~pf/
algoritmos/aulas/bubi2.html>. Acesso em: 23 mai. 2018.
CORMEN, Thomas; BALKCOM, Devin. Busca 
Binária. Khan Academy, s.d. Disponível em: <https://
pt.khanacademy.org/computing/computer-science/
algorithms/binary-search/a/binary-search>. Acesso em: 
23 mai. 2018.
Minhas anotações