Síntese: qual padrão usar?
Dois módulos, cinco padrões. Hora de treinar o reflexo: bater o olho num enunciado e saber se é busca binária, qual sabor, ou se é um problema de bits — com justificativa.
A árvore de decisão da seção
1. Os dados estão ORDENADOS (ou há uma fronteira monótona "não→sim")?
├── procurar um valor exato → BUSCA BINÁRIA clássica
├── array ORDENADO mas GIRADO → busca binária modificada
│ (qual metade está ordenada?)
├── "primeiro/último que satisfaz..." → busca binária por FRONTEIRA
└── "a MENOR/MAIOR x que funciona" → busca binária NA RESPOSTA
(testar um x candidato é O(n))
2. O problema fala em BITS, binário, ou tem restrição estranha de espaço?
├── "aparece 2x menos um" / "faltando" → XOR (pares se cancelam)
├── contar/olhar/ligar/apagar bits → operadores & | ^ ~ << >>
├── "para cada i, conte os bits" → counting bits (ans[i]=ans[i>>1]+(i&1))
└── "sem usar +", inverter bits → técnicas (carry por &<<1, espelho)
E o teste de sanidade de sempre: se o enunciado pede melhor que O(n) num dado ordenado, é quase certo que a resposta é O(log n) — busca binária.
O mapa completo da seção
| Padrão | Pergunta-chave | Tempo | Espaço |
|---|---|---|---|
| Busca binária clássica | "achar valor em array ordenado" | O(log n) | O(1) |
| Busca binária girada | "array ordenado e girado" | O(log n) | O(1) |
| Busca na resposta | "menor/maior x que satisfaz" | O(n log(faixa)) | O(1) |
| XOR | "aparece 2x menos um / faltando" | O(n) | O(1) |
| Operadores de bit | testar/ligar/apagar/contar bits | O(1)–O(largura) | O(1) |
| Counting bits | "bits 1 de 0..n" | O(n) | O(n) (saída) |
A ideia que une o módulo de busca binária: descartar metade com certeza a cada passo. A que une o módulo de bits: operar nos 0s e 1s direto, em vez de tratar o número como quantidade.
Quiz da seção
Enunciados que você não viu nas aulas. Identifique o padrão e o porquê. 7+ acertos: pronto para a prova.
🧠 Quiz da seção: Binary
0/81. 'Num array ordenado, encontre a posição onde um target deveria ser inserido para mantê-lo ordenado.' Qual padrão?
2. 'Dado um array onde todo número aparece 3x, exceto um que aparece 1x, ache o solitário.' O XOR simples resolve?
3. 'Qual a menor capacidade de um navio para transportar todos os pacotes em D dias?' Qual padrão?
4. 'Encontre o pico (um elemento maior que seus vizinhos) em O(log n).' Por que busca binária funciona mesmo sem o array ser ordenado?
5. 'Detecte se um inteiro é potência de 2.' Qual técnica de bits resolve em O(1)?
6. Qual a condição GERAL para usar busca binária, vista nesta seção?
7. Por que o XOR é preferível à 'soma de Gauss' para achar um número faltando?
8. Qual a ideia-mãe que une o MÓDULO de busca binária?
Pronto para a prova?
A prova final da seção Binary tem três problemas inéditos — fácil, médio e difícil — com casos ocultos. O difícil aplica busca binária na resposta (o sabor da árvore de decisão que talvez seja o mais surpreendente). As cinco aulas cobrem tudo que você precisa.
Boa prova! Volte para a página da seção e clique em "Prova final".