Alta Performance com Busca Binária

Um dos métodos mais comum de realizar uma busca em uma lista de opções, é procurar item a item, até encontrar a opção que corresponde à aquela que está sendo procurada. Essa metodologia de busca é conhecida como bubble search. Embora funcional, ela é horrível para a performance, porque faz com que cada elemento dentro do conjunto a ser procurado, precise ser testado, até que a opção correta seja encontrada. Assim, em uma lista de 100.000 opções por exemplo, caso a última opção seja a correta, todas as 100.000 opções precisam ser testadas.

Em uma implementação Delphi, isso geralmente está vinculado a um laço de repetição como “for” ou “while”:

 

Embora esse seja um caso necessário em alguns cenários, obviamente não é algo a ser desejado.

Quando os valores de uma lista possam ser ordenados de alguma forma, é possível criarmos alguns algorítmos otimizados para a busca desses valores. Existem diversos algorítmos recomendados para cada situação. Falaremos agora um pouco da busca binária.

Busca Binária

Quando pudermos ordenar uma lista de elementos, é possível utilizarmos a busca binária. Ela possui esse nome porque sempre que a condição do retorno é testada, ela descarta metade da lista em cada teste. Assim, ela considera que existam dois lados: o lado correto, e o lado errado (2 = BInário).

Vamos entender melhor.

Imaginemos um conjunto de números dispersos que vão de 1 a 100. A primeira coisa a ser feita, é ordenar esses números de alguma forma. No nosso exemplo, vamos ordená-los de forma crescente (1, 5, 7, 10…100). A ordenação é o passo mais importante, porque ela que cria a condição necessária para o funcionamento da busca binária.

Uma vez com a lista ordenada, vamos utilizar a seguinte lógica para buscarmos nossos valores. Sempre que formos procurar um valor, iremos sempre ao meio da lista de verificaremos se o valor do meio é o valor que procuramos. Se for, está finalizado. Caso não for, verificaremos, conforme a ordenação dada (no nosso caso, ordem crescente de números), se o número que procuramos está antes ou depois do meio. Caso esteja antes, sabemos que podemos descartar da busca a metade para frente. Caso esteja depois, sabemos que podemos descartar o início da lista até a metade. Agora, teremos apenas metade da lista para procurar novamente.

Esse trecho da metade da lista restante forma uma nova lista, menor, é verdade, mas a qual podemos aplicar a mesma lógica. Assim, para essa nova lista, resultado da lista anterior, aplicamos o mesmo princípio: vamos à metade dessa nova lista e verificamos se o valor do meio é o valor que procuramos. Se for, encontramos o elemento. Se não for, verificamos se o número que procuramos está antes ou depois do meio. Se estiver antes, a metade posterior é descartada. Se estiver depois, a metade anterior é descartada.

Essa lógica é aplicada continuamente  às novas “sublistas” até encontrarmos o resultado.

O interessante desse algorítmo é que, não importa o tamanho da lista, o valor será encontrado em até 8 etapas. Isso mesmo. Mesmo que a lista tenha 1.000.000 de elementos, em até 8 etapas, o resultado correto é retornado. Isso é fantástico quando falamos em desempenho, porque 8 etapas de processamento é muito pouco para qualquer computador processar e
retornar o valor correto.

Implementando uma busca binária

Podemos implementar uma busca binária em Delphi facilmente, utilizando o recurso da recursividade. Como teremos ao máximo 8 chamadas para o mesmo método, não haverá risco de estouro de pilha (stack overflow). Veja o código abaixo:

 

 

A primeira coisa a fazermos é checar se o valor a ser encontrado está é algum dos limites da lista. Se não for, encontramos o meio e verificamos se o elemento do meio é o elemento que procuramos. Se não for, verificamos se está para frente ou para trás da lista. Conforme o caso, chamamos novamente a função BuscaBinaria, mas alterando o “range” do valor inicial e valor final da lista. Essa é a forma de limitarmos as buscas para a metade anterior ou posterior da lista.

Lembrando que a chamada inicial da busca ocorre passando o valor inicial como o primeiro elemento da lista, e o valor
final como o último elemento da lista.

Em poucas linhas você tem uma excelente ferramenta de busca de alta performance.

Busca Binária nativa no Delphi

Documentação: http://docwiki.embarcadero.com/Libraries/Tokyo/en/System.Generics.Collections.TArray.BinarySearch

O Delphi possui uma ferramenta nativa para buscas binárias. Utilizando-se do método BinarySearch da classe TArray, é possível chegar ao mesmo resultado.

Veja o código abaixo:

 

A primeira coisa que fizemos aqui foi criar uma lista aleatória de 0 à MAX (ou 100.000). Depois definimos qual seria o valor a ser encontrado na lista. A variável “Indice” é alimentada pelo terceiro parâmetro do método, um parâmetro out que retorna o índice em que está o elemento (ou o índice mais próximo a ele). O último parâmetro do método é um método anônimo para a definição da ordenação da lista (lembra que a ordenação é muito importante para a busca binária?).

O método retorna “true” se encontrou o elemento ou “false” se ele não foi encontrado.

Muito simples não é?

Conclusão

A busca binária é uma execelente ferramenta para encontrar valores dentro de um conjunto que possa ser ordenado de alguma forma. O Delphi possui essa ferramenta implementada de forma nativa e bem flexível, pois implementa a
funcionalidade com o uso de genérics, dando a possibilidade de alterar o tipo e a metodologia de busca conforme o caso necessário. Todavia, ainda sim existem alguns casos mais complexos onde será necessário o desenvolvimento de uma busca binária própria para o problema em questão, então é importante conhecer o mecanismo de funcionamento dessa busca, para conseguir extrair o máximo de proveito de sua utilização.