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

Binary Search
Mecanismo de uma 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.

5 respostas para “Alta Performance com Busca Binária”

  1. Muito bom seus artigos, mas como fazer isso se preciso encontrar algo do tipo string darei um pequeno exemplo com apenas 3 items
    dentro de uma lista mas imagine um milhão:
    item1 = ‘036-5989-123-8’
    item2 = ‘953-6459-894-2’
    item3 = ‘206-809-035-559’
    etc….
    como usar???

    1. Olá João,

      A coisa mais importante em uma busca binária é a ordenação. É ela que garante o funcionamento de alta performance. O conteúdo em sí, de cada posição, não interfere na busca. Pense que cada elemento do seu conjunto de itens possui uma posição, e um conteúdo. O que importa é a posição, e não o conteúdo. Assim, dentro da sua lógica, o conteúdo pode ser texto, imagem, o que for necessário. Basta que você consiga ordenar isso. Essa é a mágica. Porque uma vez ordenado, o algorítmo irá de metade a metade comparando os valores, vendo se o valor atual é igual, maior ou menor que o valor esperado.

      TArray.BinarySearch possui, como um dos argumentos, uma parâmetro para identificação do mecanismo de comparação (TComparer). Se você conseguir, dentro da sua string, determinar “qual vem antes ou depois”, você pode reimplementar esse mecanismo de comparação e pronto, estará feito sua busca binária com valores strings.

      Abraços!

  2. Fiz essa função de Busca Binaria mas tive alguma dificuldade nas
    grandes quantidades:
    Quando não achado, o item procurado precisava se Inserido para
    manter a sequencia. Isso implicava em Deslocar todos os nomes
    deixando uma vaga e o tempo aumentava.
    Então resolvi Indexar cada Nome e o Deslocamento era apenas
    do Indexador (que tinha tamanho fixo) e o tempo diminuiu;
    Assim consegui contar os segmentos de numero Pi com
    um milhão de casas decimais…

    1. Laércio,

      obrigado pelo comentário.

      Não sei exatamente como você o fez, contudo a busca binária para ser efetiva precisa ser numérica e principalmente (e aqui mora a grande jogada) ser ordenada.

      Não sei se já não o fez, mas tente verificar a performance com dicionários (classe TDictionary). Elas costumam ser excelentes com relação a isso também.

      Abraços!

Deixe um comentário

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *