Algoritmo recursivo de busca binária em arrays

A operação de busca de elementos costuma ser muito aplicada em praticamente todas as estruturas de dados conhecidas. Independente do contexto de desenvolvimento de um sistema, o requisito voltado para a procura de alguma informação específica sempre está presente. E, na maioria das vezes, os usuários desses programas desejam que as suas pesquisas sejam concluídas o mais rápido possível.

Dependendo de como a aplicação se comporta, a consulta pelos dados pretendidos pode acontecer dentro do ambiente de um database, através de queries SQL. Entretanto, há situações em que a procura acaba sendo processada nos limites do próprio sistema. Nesses tipos de cenário, torna-se fundamental o uso de algoritmos de busca eficientes, que localizem o conteúdo solicitado sem demora.

O catálogo de algoritmos do segmento de pesquisa possui uma diversidade notável. Existem inúmeras opções disponíveis para que os programadores apliquem nos seus projetos. Contudo, vale ressaltar que o algoritmo com maior popularidade do ramo em questão é o da busca binária. A sua implementação para arrays no formato recursivo será analisada em detalhes no decorrer deste artigo.

Entendendo o algoritmo

Imaginemos um vetor formado pelos itens 10, 20, 30, 40 e 50, no qual haja a necessidade de determinar o índice do número 40. Adotando uma abordagem tradicional, denominada busca linear, esse elemento seria encontrado a partir de uma varredura completa na estrutura. 

A adesão deste modelo de busca funciona bem em arrays enxutos, que apresentam uma capacidade pequena como no vetor exemplificado acima. Todavia, quando a quantidade de elementos cresce razoavelmente, o custo gerado pela complexidade de tempo aumenta em proporções impressionantes.

Engenhosamente, a busca binária promove um aperfeiçoamento da performance de execução das operações de pesquisa. Para alcançar essa melhoria, cabe frisar, os arrays e demais estruturas devem estar ordenados.

Partindo da precondição supracitada, o algoritmo divide de maneira repetida o intervalo de busca dos vetores pela metade. Desse modo, a complexidade de tempo migra de um patamar linear para um grau logarítmico.

1. A busca começa com o item intermediário do array.
2. Se o elemento procurado e o intermediário forem iguais, a busca chega ao fim.
3. Caso contrário, se o elemento procurado for menor que o intermediário, o intervalo da pesquisa passa por uma redução para a metade inferior do vetor.
4. Senão, se o elemento procurado for maior que o intermediário, o intervalo da pesquisa passa por uma redução para a metade superior do vetor.
5. A lógica do algoritmo é repetida até que o número seja encontrado ou o intervalo de busca acabe.

O passo a passo do algoritmo pode ser elucidado com base no array hipotético composto pelos itens 10, 20, 30, 40 e 50. Novamente, supondo que o número 40 precisasse ser identificado, a busca binária realizaria as seguintes instruções.

1. O primeiro elemento intermediário do array seria o número 30, dado que a divisão por dois da soma do índice inferior inicial (zero) com o índice superior inicial (quatro) resulta justamente no índice dois. Como se sabe, o item 30 é menor do que o 40, e por conta disto o intervalo de pesquisa passa por uma redução para a metade superior. Isso ocorre atribuindo o índice do ponto médio (dois) incrementado em um para o índice inferior.
2. Agora, o segundo elemento intermediário do array seria o número 40, tendo em vista que ao dividir por dois a soma do índice inferior (três) com o índice superior (quatro) obtêm-se o índice três. Com isso, a busca é encerrada logo na segunda comparação realizada pelo algoritmo.

Usando a implementação recursiva do algoritmo

A busca binária, assim como a boa parte dos seus pares, a exemplo da busca ternária, possui uma implementação recursiva e outra iterativa. Em termos de complexidade de tempo, as duas formas se equivalem, executando logaritmicamente. 

Porém, analisando o consumo do espaço auxiliar de memória, enquanto a abordagem iterativa detém uma complexidade constante, o procedimento recursivo, que será mostrado a seguir, dispõe de uma complexidade logarítmica. 

A função recursiva recebe quatro parâmetros, sendo o primeiro deles o vetor examinado. O segundo parâmetro determina o índice do limite inferior (esquerda) da busca, inicializado por padrão em zero. Já o terceiro parâmetro estabelece o índice do limite superior (direita) da busca, inicializado por padrão com o valor do último índice do array de input. Enfim, o quarto parâmetro indica qual número será pesquisado na estrutura. 

1. O método verifica se o intervalo da direita supera ou iguala o intervalo da esquerda. Em caso afirmativo, o fluxo de execução do algoritmo continua. Senão, a rotina retorna o número -1, sinalizando que a busca terminou sem localizar o número x.
2. A variável metade é declarada para armazenar o índice do elemento intermediário. O seu valor origina-se de uma divisão por dois da soma dos índices do limite inferior (esquerda) e superior (direita).
3. Se o elemento intermediário for igual ao número x, a função retorna o índice do elemento intermediário (metade), terminando a busca com sucesso.
4. Se o elemento intermediário for maior do que o número x, o método encurta o intervalo de pesquisa para a metade inferior, fazendo uma chamada recursiva na qual o parâmetro direita recebe o índice intermediário (metade) decrementado em um.
5. Se o elemento intermediário for menor do que o número x, o método encurta o intervalo de pesquisa para a metade superior, fazendo uma chamada recursiva na qual o parâmetro esquerda recebe o índice intermediário (metade) incrementado em um.

Comparando o desempenho do algoritmo com a busca linear

Conforme mencionado anteriormente, a busca linear figura na lista dos algoritmos mais triviais de pesquisa. Isso porque a sua implementação não possui grandes segredos, bastando percorrer com um laço for todos os elementos do vetor, e checar a cada iteração se o item atual corresponde ao procurado.

Em virtude da busca linear inspecionar o array do começo até o fim, isto pensando no pior cenário em que o elemento pesquisado está na última posição da estrutura, a sua complexidade de tempo obviamente é linear. Ou seja, a medida que vetores de maior capacidade precisam ser examinados por esse algoritmo, mais tempo de processamento acaba sendo necessário.

A busca binária resolve o problema da busca linear, reduzindo a complexidade de tempo para um nível logarítmico. Melhor dizendo, a busca binária precisa executar menos passos para encontrar qualquer elemento dentro de um vetor. Essa diferença pode ser notada comparando os dois algoritmos.

Método	Input	Média de tempo	Espaço alocado
MétodoBuscaBinaria	InputInt32[10]	Média de tempo4.379 ns	Espaço alocado-
MétodoBuscaLinear	InputInt32[10]	Média de tempo4.614 ns	Espaço alocado-
MétodoBuscaBinaria	InputInt32[100]	Média de tempo9.404 ns	Espaço alocado-
MétodoBuscaLinear	InputInt32[100]	Média de tempo43.670 ns	Espaço alocado-
MétodoBuscaBinaria	InputInt32[200]	Média de tempo11.413 ns	Espaço alocado-
MétodoBuscaLinear	InputInt32[200]	Média de tempo79.374 ns	Espaço alocado-
MétodoBuscaBinaria	InputInt32[300]	Média de tempo13.889 ns	Espaço alocado-
MétodoBuscaLinear	InputInt32[300]	Média de tempo111.928 ns	Espaço alocado-
MétodoBuscaBinaria	InputInt32[1000]	Média de tempo15.089 ns	Espaço alocado-
MétodoBuscaLinear	InputInt32[1000]	Média de tempo401.359 ns	Espaço alocado-

Conjecturando uma pesquisa feita em um vetor de dez elementos, a busca linear e a busca binária praticamente se equiparam no que tange a complexidade de tempo. Entretanto, quando elevamos a quantidade de itens para cem, a busca binária passa a ser executada quase cinco vezes mais rápida.

A discrepância aumenta a cada novo cenário: com duzentos elementos, a busca binária atinge um ganho de sete vezes, ao passo que para trezentos elementos, a vantagem se estende para oito vezes. Enfim, na casa dos mil itens, a disparidade é extremamente notória, posto que a busca binária processa com uma velocidade maior de vinte e seis vezes.

O código-fonte completo do algoritmo recursivo da busca binária e os detalhes extras a respeito da sua performance estão disponíveis no meu repositório do Github.