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?

 

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.

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.