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.