O problema de busca consiste em avaliar se um elemento de mesmo tipo da sequência está contido na sequência ou não está contido em uma sequência.
A definição de um problema define quais são as saídas possíveis de um problema, quais as respostas esperadas para sua solução e quais as saídas para estas soluções. Em computação, para o problema de busca, existem dois valores de entrada para solucionar este problema: a sequência e o elemento chave (objeto de busca); e as saídas possíveis são: verdadeiro (elemento encontrado) e falso (elemento não encontrado), ou seja, um booleano.
Assim, uma instância de um problema de busca contem uma sequência e o elemento chave. E, para cada instância, existe uma solução diferente.
Um exemplo de uma instância do problema de busca é dada por:
| Chave | Sequência | |||||
|---|---|---|---|---|---|---|
| $x=8$ | Posição | 0 | 1 | 2 | 3 | 4 |
| Elemento | 6 | 4 | 2 | 8 | 10 | |
Desta forma, observa-se que a solução para esta instância é verdadeiro, pois o elemento 8 está contido na sequência.
O desafio do problema é desenvolver um algoritmo que seja capaz de resolver esta operação de acordo com a definição apresentada.
Uma sequência é um tipo abstrato de dado (TAD) que pode ser implementado por uma estrutura de dado do tipo vetor (ou arranjo). Logo, também podemos representar o problema de busca em um computador utilizando o conceito de vetor.
Em uma operação de busca, o número máximo de elementos da sequência não é alterado. Assim, a quantidade de elementos do vetor que representa esta sequência não necessita ser alterado durante a operação. Contudo, uma sequência pode estar contida dentro de um vetor que comporta uma quantidade superior de elementos. Desta forma, cabe atentar que o número máximo de elementos da sequência define o espaço de busca para a realização da operação.
Em uma operação de busca são necessários saber: a primeira posição (v*), a quantidade de elementos inseridos neste vetor ($n$) e o elemento chave ($x$).
| Posição | Quantidade | Chave | Vetor | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| #00FF01 | $n=5$ | $x=8$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 6 | 4 | 2 | 8 | 10 | – | – | – | – | – | ||||
Um algoritmo de busca, fundamentalmente, segue três operações em um loop:
- Escolhe uma posição da sequência;
- Acessa o elemento da posição escolhida;
- Compara o elemento acessado ao elemento chave de busca.
O critério de parada deste loop é quando a comparação for verdadeira ou quando não houver mais registros (posição) para avaliar.
A diferença entre algoritmos de busca são estratégias de escolha da posição de sequência a ser avaliada. O algoritmo mais eficiente para efetuar uma busca é aquele em que a estratégia adotada obtenha a solução com o menor número de comparações.
Iremos avaliar dois algoritmos para a solução do problema de busca: a busca sequencial e a busca binária. Ambos os algoritmos resolvem o mesmo problema e utilizam as informações sobre o mesmo espaço de busca para facilitar o processo de busca.
Busca Sequencial
A estratégia de escolha de um algoritmo de busca sequencial consiste em escolher uma posição a partir da primeira posição para à posição seguinte e assim sucessivamente, até o último elemento do vetor.
O algoritmo de busca sequencial pode realizar a operação de busca de forma crescente ou decrescente.
Algoritmos de busca sequencial em sua implementação iterativa em C:
Algoritmos de busca sequencial em sua implementação recursiva em C:
Busca Binária
A busca binária vai utilizar a maneira como os dados estão organizados entre si para reorganizar a sequência recursivamente até que uma solução seja encontrada. Mais especificamente, em uma busca binária se divide o espaço de busca entre uma parte que foi avaliada e outra que será avaliada. Par tal, é necessário que a sequência de busca esteja ordenada:
| Posição | Quantidade | Chave | Vetor | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| #00FF01 | $n=5$ | $x=8$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 2 | 4 | 6 | 8 | 10 | – | – | – | – | – | ||||
A ordem da sequência pode ser crescente ou decrescente, a depender da natureza da busca a ser realizada.
A estratégia de escolha de um algoritmo de busca binária consiste em utilizar esta sequência ordenada para escolher uma posição a ser comparada em sua busca. Para isso é escolhido uma posição arbitária na sequência. Na busca binária, se é arbitrado a posição central da sequência:
| Posição | Quantidade | Chave | Vetor | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| #00FF01 | $n=5$ | $x=8$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 2 | 4 | 6 | 8 | 10 | – | – | – | – | – | ||||
Uma vez escolhida a posição, este valor é acessado e comparado ao elemento chave. Nesta comparação, existem três possibilidades de casos:
- O elemento é igual ao elemento chave: a busca é encerrada;
- O elemento é maior que o elemento chave: o espaço de busca é reduzido à parte inferior do vetor;
- O elemento é menor que o elemento chave: o espaço de busca é reduzido à parte superior do vetor.
Em nosso exemplo, o elemento é menor que o elemento chave $(5<8)$, logo, o espaço de busca é reduzido à parte superior do vetor:
| Posição | Quantidade | Chave | Vetor | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| #00FF01 | $n=5$ | $x=8$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 2 | 4 | 6 | 8 | 10 | – | – | – | – | – | ||||
e assim sucessivamente, até o último elemento do vetor.
Algoritmo de busca binária em sua implementação iterativa em C:
Algoritmo de busca binária em sua implementação recursiva em C:
Um algoritmo de busca binária reduz substancialmente a quantidade de registros que se necessita acessar a cada comparação. Arbitrada a posição central da sequência, este número se reduz pela metade $ (n/2) $, ou seja, o algoritmo de busca binária reduz o espaço de busca pela metade a cada passo. Estes “saltos mais largos” entre os registros até a solução tornam o algoritmo de busca binária mais eficiente para sequencias de muitos elementos.
Referências
- PIVA JÚNIOR, Dilermando (et al). Estrutura de dados e técnicas de programação. 1. ed. Rio de Janeiro, RJ: Campus, 2014. 399 p. ISBN: 9788535274370.
- CORMEN, Thomas H et al. Algoritmos: teoria e prática. Rio de Janeiro: Elsevier, 926 p. ISBN: 9788535236996.
- TOSCANI, Laira Vieira; VELOSO, Paulo A. S. Complexidade de algoritmos: análise, projeto e métodos. 3. ed. Porto Alegre: Bookman, 2012. 261 p. (Série livros didáticos informática UFRGS, 13) ISBN: 9788540701380.
- ASCENCIO, Ana Fernanda Gomes. Estruturas de dados: algoritmos, análise da complexidade e implementações em Java e C/C++. São Paulo: Pearson, c2010. 432 p. ISBN: 9788576052216, 978857605816.
- BRASSARD, Gilles; BRATLEY, Paul. Fundamentals of algorithmics. Englewood Cliffs: Prentice Hall, c1996. xx, 524 p. ISBN: 0133350681.
Livraria
