Busca binária e o jogo de adivinhar o número
A busca binária é ensinada nos livros básicos de algoritmos. Nunca achei que iria usá-la. Só que, anos depois, eis que precisei utilizar na prática…
Este algoritmo pode ser utilizado para adivinhar um número. Pense num número de 1 a 100.
A cada palpite, a outra pessoa só pode dizer “maior”, “menor” ou “acertou”. Qual a melhor estratégia? Ora, o melhor é eliminar o máximo possível de candidatos a cada rodada. Divida a lista bem ao meio (50), depois faça o mesmo para a parte superior ou inferior, etc.
A complexidade computacional da busca binária é O(log(N)), onde N é o tamanho da lista. Se fosse para percorrer todos os itens, seria O(N). Ou seja, ganhamos uma ordem de grandeza de processamento nessa brincadeira. Premissa: a lista deve estar ordenada.
Ok, é uma curiosidade legal, mas e aí?
Get Arnaldo Gunzi’s stories in your inbox
Join Medium for free to get updates from this writer.
Aí que, em projeto recente, tivemos que consultar um CEP dada uma lista de faixas de CEPs e preços.
A primeira abordagem algorítmica foi: jogar num DataFrame, usa o “filter” e pronto, temos a linha da tabela. Só que essa abordagem é exatamente o caso bruto acima, ele vai percorrer todas as linhas até achar.
Se fosse para rodar uma vez só, qualquer algoritmo serviria. Só que esta consulta, feita milhares de vezes ao dia, começa a pesar.
Neste caso específico, a tabela de CEPs já é ordenada, o que possibilita que utilizemos a busca binária. A IA pode ajudar a escrever a rotina. O ponto é saber onde utilizar ou não.
Outro caso é procurar uma palavra num dicionário (em papel). Abrimos numa página aleatória. Se estiver em “M” e a nossa palavra começar em “C”, tentamos outra página na metade inferior, e assim sucessivamente. Mais louco ainda é dicionário de Kanji, aí fica para outro papo.
Quem diria que um joguinho de criança poderia ser tão útil?
Nota: Com colaboração do Antoniobrandaolima
