Texto de: Geraldo Daros
Introdução
A busca binária é uma ferramenta fundamental em ciência da computação, feita para localizar um elemento específico em um conjunto de dados ordenados. Sua eficácia está na abordagem de divisão do espaço de busca pela metade a cada iteração. Isso significa que, mesmo em conjuntos de dados extensos, a busca binária pode localizar um elemento em um número relativamente pequeno de etapas, tornando-a uma técnica interessante para otimização de desempenho.
O que é busca binária?
A busca binária é um algoritmo eficiente projetado para operar em conjuntos de dados ordenados. Em sua essência, a busca binária procura um elemento específico em um escopo definido, sendo uma lista ordenada, utilizando informações sobre a posição relativa desse elemento na lista. Ao receber feedback sobre se o valor pesquisado está acima ou abaixo durante cada iteração, a busca binária otimiza sua trajetória. A busca binária segue um processo sistemático e eficiente: primeiro, divide-se o intervalo em duas partes iguais e verifica-se se o número buscado está na metade selecionada, exemplo: intervalo de 0 a 100, divide-se e pega a metade, 50. Com base nessa comparação, vamos ter a resposta se o número que buscamos é 50, abaixo ou acima dessa metade(50). Esse procedimento é repetido sucessivamente até que o número desejado seja encontrado.
Descobrindo um número eficientemente
Vejamos busca binária, na prática. Se eu falar que estou pensando um número aleatório de 0 a 200 e que a cada vez que você me falar um número direi se seu palpite é menor ou maior do número objetivo, você precisaria de no máximo quantas chances para acertar o número que estou pensando? Pense e tente responder antes de prosseguir.
Conseguiu responder? Se não conseguiu, não se desespere. Isso não é uma tarefa fácil e geralmente leva alguns bons minutos se você nunca viu busca binária.
Como você faria para descobrir o número? Poderia simplesmente tentar adivinhar falando números aleatórios e então você poderia precisar de 200 chances. Mas há uma forma otimizada de fazer isso. Primeiro pegamos o escopo total, são 200 números, depois, quebramos esse valor ao meio e fazemos o palpite com exatamente o número que restou depois da quebrarmos o número, e continuamos fazendo isso para a direção correta até encontrarmos o número certo.
Como faríamos os cálculos:
200 / 2 = 100 O número é 100? Não, é maior.
Então precisamos da parte maior. Novo escopo é de 100 a 200. Metade de 100 até 200 = 150. O número é 150? Não, é maior.
Novamente, precisamos da maior parte, pegamos de 150 a 200. Metade de 150 até 200 = 175. O número é 175? Não, é menor.
Agora pegaremos a menor parte, sendo 150 a 175. Metade de 150 até 175 = 162,5, nesse caso, vamos arredondar. O número é 163? Não, é menor.
Novamente, precisamos da menor parte, sendo 150 a 163. Metade de 150 até 163 = 156,5, nesse caso, vamos arredondar. O número é 156? Não, é menor.
Novamente, precisamos da menor parte, sendo 150 a 156. Metade de 150 até 156 = 153. O número é 153? Não, é menor.
Novamente, precisamos da menor parte, sendo de 150 a 153. Metade de 150 até 153 = 151,5, arredondando para baixo. O número é 151? Não, é maior.
Só restou um número, mas continuaremos como anteriormente. Agora, precisamos da maior parte, de 151 a 153. Metade de 151 até 153 = 152. O número é 152? Sim, é! Parabéns, encontramos o número.
E é dessa forma que funciona o algoritmo de busca binária, agora você sabe um novo algoritmo!
Código para adivinhar número com busca binária
Nada melhor que ver na prática, não é mesmo? Proponho verificarmos um algoritmo em Java que adivinha o número que o usuário está pensando.
import java.util.Scanner;
public class BuscaBinaria {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println("Pense em um range, de 0 até x e digite o valor de x.");
int range = Integer.parseInt(scanner.nextLine());
System.out.println("""
Agora pense em um número no meio desse range.
"Responda 'menor' se o número que você está pensando é menor do que o palpite."
"Responda 'maior' se o número que você está pensando é maior do que o palpite."
"Responda 'acertou' se o palpite estiver correto.
""");
int min = 0;
int max = range;
int palpite;
int passos = 1;
while (true) {
palpite = (min + max) / 2;
System.out.println("É " + palpite + " o número que você está pensando?");
System.out.print("Responda 'menor', 'maior' ou 'acertou': ");
String resposta = scanner.nextLine().toLowerCase();
if (resposta.equals("acertou")) {
passos++;
break;
} else if (resposta.equals("menor")) {
passos++;
max = palpite - 1;
} else if (resposta.equals("maior")) {
passos++;
min = palpite + 1;
} else {
System.out.println("Por favor, responda apenas 'menor', 'maior' ou 'acertou'.");
continue;
}
if (max == min) {
System.out.println("Descobri. O número que você está pensando é: " + (max - 1));
break;
}
}
System.out.println("Número de passos necessários: " + passos);
System.out.println("Máximo de passos que poderiam ser necessários: " + log2(range));
scanner.close();
}
public static int log2(int N) {
return (int) Math.ceil(Math.log10(N) / Math.log10(2));
}
}
Esse simples algoritmo fará algumas perguntas ao usuário e então adivinhará o número que o usuário está pensando. O foco não foi em produzir um código sem chances de dar errado, reutilizável e bonito, mas sim mostrar como poderia ser feito um algoritmo para buscar um elemento usando pesquisa binária de forma simples.
Este código opera da seguinte maneira: inicialmente, pedimos ao usuário que defina um intervalo, normalmente de 0 até um valor específico, representado por range. Em seguida, o sistema calcula a metade entre 0 e range e faz um palpite. Com base na resposta do usuário, se o palpite está correto, abaixo ou acima do valor pensado, o sistema atualiza os valores mínimo e máximo do intervalo. Assim, o próximo palpite é obtido como a metade desses dois valores atualizados. Trata-se de um algoritmo simples e eficaz, não acha?
Desempenho
A busca binária se sobressai muito em comparação a busca linear, basicamente, se você fosse buscar um elemento de 0 até 100 com busca linear, iria precisar de no máximo 100 tentativas, já com a busca binária de no máximo 7. Agora pensando em grande escala, com 2 milhões (200000000) na busca linear talvez seria necessário 2 milhões de tentativas, claro, considerando o pior dos casos, já usando a busca binária, somente 28 tentativas. Absurdo, não?
A busca binária é executada com tempo logaritmo, especificamente o logaritmo de n na base 2. Caso o tópico de logaritmos não esteja clado para você, sugiro que faça um breve estudo sobre o tema para compreendê-lo melhor.
Conclusão
Em resumo, a busca binária surge como uma ferramenta indispensável em ciência da computação, oferecendo uma abordagem eficiente para localizar elementos em conjuntos de dados ordenados. Sua estratégia de divisão sistemática do espaço de busca pela metade permite encontrar um elemento com um número mínimo de iterações, mesmo em conjuntos de dados extensos. Por meio de uma explicação passo a passo e um exemplo prático, vimos como a busca binária pode ser aplicada de forma eficaz para encontrar um número específico em um intervalo.
Além disso, ao comparar seu desempenho com a busca linear, fica evidente que a busca binária supera significativamente a busca linear em termos de eficiência, especialmente em conjuntos de dados grandes. Com sua complexidade de tempo logarítmica, a busca binária oferece uma vantagem distinta, reduzindo drasticamente o número de iterações necessárias para encontrar um elemento.
