Início de uma série de estudos sobre o livro Entendendo Algoritmos de Aditya Y. Bhargava.

Esse livro foi indicado por uma amiga, Ana Paula Mendes, e eu não imaginava o quanto iria gostar. A leitura é leve, clara e muito acessível. Se você, como eu, tem dificuldade em manter a constância em leituras técnicas, esse livro é um achado, fácil de entender, ótimo para aprender ou revisar conceitos.

Ele apresenta ideias da ciência da computação que estão no nosso dia a dia, muitas vezes sem que a gente perceba.

Uma das coisas que mais me chamam atenção nesse livro é o jeito como o autor ensina, sempre com exemplos. Em vez de encher de símbolos e fórmulas, ele quer que a gente visualize os conceitos. Ele acredita, e eu concordo, que aprendemos melhor quando conseguimos relacionar o conteúdo com algo que já conhecemos. E, pra isso, os exemplos ajudam muito.

E o melhor é que ele desenha 🤩! Sabe aquela frase “quer que eu desenhe pra você entender”? Eu respondo “sim, por favorrrrr!” e ele realmente desenha. É maravilhoso ✨.

Dá pra sentir que tudo foi pensado com cuidado, desde o conteúdo, os exemplos ilustrados até a recapitulação no fim de cada capítulo.

Depois dessa introdução, bora ver o que o capítulo 1 ensina.

A busca binária em resumo

Pensa numa lista telefônica com 1 milhão de nomes. Olhar folha por folha seria um pesadelo, né? Agora, e se eu te dissesse que dá para encontrar qualquer nome em no máximo 20 tentativas? 👀

O truque é simples: a cada etapa, tu elimina metade das opções. Comece considerando o elemento que está bem no meio da sequência. Em uma lista telefônica, isso seria abrir o livro bem no meio. Em uma lista com 10 itens, isso seria pegar o 5o item. Agora compare esse item do meio com o que você está buscando: se eles forem iguais, parabéns, você encontrou o que procurava! Agora, se o item que você encontrou for MAIOR que o item que você procura (no caso de nomes em uma lista telefônica, pense em qual nome vem primeiro na ordem alfabética), quer dizer que o item buscado está na primeira metade da lista. Caso contrário, o item está na segunda metade da lista. E assim você consegue cortar a lista pela metade apenas comparando o item procurado com o item do meio. Depois disso, basta pegar a parte que você selecionou e aplicar a mesma estratégia, checando o item do meio e descartando metade da lista. Observação: Essa técnica só funciona se a lista de itens estiver ordenada!

E o mais legal é que, mesmo que a lista dobre de tamanho, tu só precisa de mais uma etapa para chegar ao resultado. 🤓

Exemplo: Para facilitar a conta, vamos pegar uma lista menor de 128 nomes e calcular o número máximo de etapas que levaríamos para encontrar um nome específico. Logo em seguida, dobramos o tamanho da lista e vemos que isso adiciona apenas mais uma etapa:

def max_etapas(n):
    etapas = 0
    while n > 1:
        n //= 2
        etapas += 1
    return etapas

print(max_etapas(128)) # 7
print(max_etapas(128*2)) # 8

Observação importante: numa lista telefônica física, a gente já sabe pular quase direto para a letra certa, o que lembra mais o funcionamento de um hashmap (ou dict no Python), que encontra um item em tempo constante. Mas no computador, quando temos apenas uma lista ordenada (como [1, 3, 5, 7, 9, 11, 13]), não existe esse “pulo mágico”, é aí que a busca binária pode ajudar, cortando a lista ao meio de forma sistemática até encontrar (ou concluir que o elemento não está lá).

Legal né? Isso é ciência da computação!! 💁‍♀️✨

Exemplos básicos de busca binária:

Pense em um número entre 1 e 100. Dá para adivinhar em, no máximo, 7 tentativas:

Minha primeira pergunta: “É 50?”

• Se você disser “maior”, eu sei que está entre 51 e 100
• Se disser “menor”, está entre 1 e 49

Segunda pergunta: Digamos que seja maior que 50. “É 75?” (meio entre 51 e 100)

• Maior? Está entre 76 e 100
• Menor? Está entre 51 e 74

E assim por diante, sempre eliminando metade das possibilidades.

Vamos ver como fica com uma quantidade maior de números:

Sim, 20 tentativas para encontrar algo entre 1 milhão de opções! 🚀

Esse “milagre” da busca binária acontece por causa de um conceito chamado logaritmo, e já já eu te mostro o porquê.

Agora que você já entendeu a busca binária, vamos entrar em mais três pontos que andam de mãos dadas: logaritmos, tempo de execução e notação Big O.

Preparei um resumo rápido de cada um, do jeito que fez sentido pra mim. Se em algum momento ficar confuso, não tem problema, dá uma olhada no livro que é sucesso 🫂💖

Logaritmos:

O número máximo de tentativas na busca binária é dado por log₂(n), logaritmo na base 2 de n.

Se o nome assusta, pensa assim:

log₂(n) é o número de vezes que você precisa dividir n por 2 até chegar em 1

Exemplo:

• log₂(128) = 7, 7 cortes ao meio até sobrar 1 item
• log₂(256) = 8, só mais uma etapa, mesmo dobrando o tamanho da lista

A base “2” vem justamente porque a cada passo cortamos a lista pela metade.

Tempo de execução:

Sempre que falamos sobre um algoritmo, é importante pensar no tempo de execução, quanto esforço (ou quantos passos) ele precisa para chegar ao resultado.

Na busca linear (a pesquisa simples), verificamos item por item:

• Lista com 100 números → até 100 tentativas
• Lista com 4 bilhões de números → até 4 bilhões de tentativas

O tempo de execução cresce na mesma proporção que o tamanho da lista. Chamamos isso de tempo linear.

A busca binária é um outro mundo:

• Lista com 100 números → no máximo 7 tentativas
• Lista com 4 bilhões → no máximo 32 tentativas

Isso acontece porque a busca binária corta as possibilidades pela metade a cada passo. Esse tipo de crescimento é chamado de tempo logarítmico.

Notação Big O

A notação Big O é um jeito de medir a eficiência de um algoritmo, mostrando como o tempo de execução cresce conforme aumentamos o tamanho da entrada.

• O(log n), tempo logarítmico (ex: pesquisa binária)
• O(n), tempo linear (ex: pesquisa simples)
• O(n * log n), um algoritmo rápido de ordenação, como quicksort (Capítulo 4)
• O(n²), um algoritmo de ordenação mais lenta, como ordenação por seleção (Capítulo 2).
• O(n!), um algoritmo extremamente lento, como o do caixeiro viajante (Capítulo 1).

O livro ilustra isso de forma bem visual e intuitiva: cresce linearmente, cresce em log, cresce muito, cresce lento… e por aí vai.

Agora que vimos como a busca binária funciona, vale notar que ela não está restrita a livros, ela aparece em várias situações do nosso dia a dia

• Sistemas de busca (Google, WhatsApp, Spotify): por trás, usam variações de busca binária em listas ordenadas ou índices.
• Filtragem de dados: encontrar rapidamente um registro específico em planilhas ou bases de dados grandes.
• Depuração de código: reduzir o espaço do problema pela metade a cada teste para achar onde o bug está.

Observação: para que a busca binária funcione, os dados precisam estar ordenados.

Vamos praticar rapidinho?

Aqui está uma lista ordenada de números: [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32]

Tente encontrar o número 22 de duas formas:

1. Busca linear: Vá um a um desde o 2.
2. Busca binária: Comece no meio, elimine metade a cada passo.

Compare quantos passos cada método precisou

Curiosidades

• O git tem uma funcionalidade chamada git bisect que usa busca binária para ajudar desenvolvedores a encontrarem bug
• Se o item que estamos buscando for o primeiro item da lista, esse é o melhor caso na busca linear e o pior caso na busca binária
• A implementação do sortedcontainers usa busca binária (a partir do módulo bisect), veja aqui

Exercícios recomendados 👩🏻‍💻💞

Para reforçar o aprendizado, aqui vão alguns desafios práticos:

LeetCode

• Binary Search — implementação direta.

• Search Insert Position — variação para encontrar onde inserir um número.

• First Bad Version — busca binária aplicada em API.

Exercism

• Binary Search (Python Track) — implementação e testes.

Dica: resolva primeiro o problema sem olhar a solução e depois compare com implementações otimizadas.

E assim começa meu roadmap de estudo: cada capítulo do livro vem acompanhado de exercícios para fixar o conteúdo.

Compartilhar: