Olá caro amigo leitor. Imagine que você está num programa de TV participando de desafio com 9 portas numeradas. Em alguma destas portas há um prêmio de R$ 900,00.
O apresentador do programa pode responder qualquer pergunta sua com um “Sim” ou “Não“. Contudo, cada resposta “Não” retira R$ 100,00 do prêmio.
Qual estratégia você utilizaria para encontrar o prêmio, perdendo o mínimo de dinheiro possível?
Imagem 1: Diversas portas agrupadas de 3 em 3 e numeradas de 1 a 9.
Iniciando com Força Bruta
Dado esse cenário, podemos imaginar algumas estratégias para você se dar bem.
A primeira hipótese que podemos experimentar é uma tática conhecida no mundo da Ciência da Computação como Força Bruta. Que consiste basicamente em ir perguntando de forma ordenada ao apresentador onde está o prêmio (“O prêmio está na Porta 1? O prêmio está na Porta 2 ?…”) até encontrá-lo.
Esta estratégia além de ser bastante simples é tentadora, porque no Melhor Caso (o prêmio estar na primeira porta) você irá levar pra casa R$ 900,00.
Porém, para o Pior Caso (o prêmio estar na nona porta) você irá sair com apenas R$ 100,00 porque irá ter recebido 8 “nãos” do apresentador.
Ou seja, a resultado da Força Bruta muda completamente no Pior e no Melhor Caso.
Busca Binária
A busca binária é uma estratégia que inicialmente pode parecer mais trabalhosa, mas possui a grande vantagem de entregar resultados que não são tão variáveis quanto os apresentados acima.
Basicamente, o Algoritmo consiste em adotarmos os seguintes passos:
1 — Eleger um elemento da esquerda e um da direita. Representando respectivamente o início e o fim do conjunto.
2 — Escolher um elemento para ser o Pivot dentre os disponíveis do conjunto. A regra para eleger esse Pivot é a seguinte:
Some o primeiro elemento da esquerda e o último elemento da direita e divida o valor dessa soma por 2. Arredonde pra cima no caso de elementos que tenham a casa decimal maior que 5.
No nosso exemplo de nove portas, o Pivot será o número 5, uma vez que ((1+ 9) / 2) = 5.
Figura 2: Imagem em preto e branco com homem de terno, no centro de um container. Nesse container há portas de metal fechadas na Direita e Esquerda. Este homem está olhando de forma indecisa para uma delas.
A obtenção do Pivot nos permite realizar uma pergunta um pouco mais elaborada ao apresentador do programa. Podemos agora perguntar pra ele: a porta onde está o prêmio,é maior ou igual a de número 5?
E é nesse ponto que mora a elegância do Algoritmo de Busca Binária. Assumindo que o apresentador respondeu “Sim”, nós podemos ignorar todas as portas menores que 5 (de 1 a 4) e repetir o trabalho nas portas restantes.
De novo, elegemos o elemento da esquerda e o elemento da direita das opções restantes (respectivamente o 5 e o 9) re-calculamos o pivot (5 +9) / 2) = 7 e perguntamos ao apresentador: a porta onde está o prêmio,é maior ou igual a de número 7?
Spoiler: seja qual for a resposta dele, na próxima interação já conseguimos descobrir onde está o prêmio.
Conclusão
Tentei te apresentar esse Algoritmo clássico de uma forma lúdica, mas recomendo que você complemente seu aprendizado com outras fontes, que possuam o rigor Matemático mais aprofundado.
Acredite que, entender bem o comportamento das buscas binárias, vai abrir o seu caminho para outros tópicos como Ataques por dicionário, Ordenação por Heap Sort, Quick Sort e Árvores Binárias.
O que posso dizer de forma resumida é que se o crescimento da quantidade de dados a serem checados for Exponencial, a eficiência desse Algoritmo fica ainda mais nítida. Porque ele possui Complexidade Logarítima.
Dado que Logaritmos são o oposto de Exponenciais nós precisaríamos, por exemplo, realizar apenas 10 interações para encontrar o prêmio em 1024 portas. (Uma vez que o log de 1024 na base 2 é 10).
Te agradeço pela leitura e fique a vontade para continuarmos a conversa nos comentários.
