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”:
1 2 3 4 5 6 7 8 9 10 |
function BuscaIndiceDaLista(ALista: TList<Integer>; ANumeroASerEncontrado: Integer): Integer var I: Integer; begin Result := -1; for I := 0 to ALista.Count - 1 do begin if ANumeroASerEncontrado = ALista[I] then Result := I; end; end; |
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
function BuscaBinaria(ALista: TList<Integer>; ANumeroASerEncontrado, AValorInicial, AValorFinal: Integer): Integer; var Meio: Integer; begin if ALista[AValorInicial] = ANumeroASerEncontrado then begin Result := AValorInicial; end else begin if ALista[AValorFinal] = ANumeroASerEncontrado then begin Result := AValorFinal; end else begin Meio := Trunc((AValorFinal - AValorInicial) div 2) + AValorInicial; if ALista[Meio] = ANumeroASerEncontrado then begin Result := Meio; end else begin if ALista[Meio] > ANumeroASerEncontrado then begin Result := BuscaBinaria(ALista, ANumeroASerEncontrado, AValorInicial, Meio); end else begin Result := BuscaBinaria(ALista, ANumeroASerEncontrado, Meio, AValorFinal); end; end; end; end; end; |
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
procedure TForm1.Button1Click(Sender: TObject); const MAX = 100000; var Lista: Array[0..MAX - 1] of Integer; ValorASerEncontrado: Integer; I: Integer; Indice: Integer; begin //Cria a lista com os valores aleatórios Randomize; for I := 0 to MAX - 1 do begin Lista[I] := Random(MAX); end; //Define qual o valor a ser encontrado ValorASerEncontrado := StrToInt(Edit1.Text); if TArray.BinarySearch<Integer>(Lista, ValorASerEncontrado, Indice, TComparer<Integer>.Construct(function(const T1, T2: Integer): Integer begin Result := T1 - T2; end)) then begin Edit2.Text := Indice.ToString; end else begin Edit2.Text := 'Não encontrado. O número mais próximo é: ' + Lista[Indice].ToString + ' de índice ' + Indice.ToString; end; end; |
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.
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???
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!
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…
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!