Padrão 1: Busca Binária
A ideia é a de procurar um nome numa lista telefônica: você não começa na primeira página — abre no meio e decide para que lado ir. Cada decisão elimina metade do que restava.
Tente primeiro: Binary Search
Antes de ler a teoria, tente resolver. Pode começar pela força bruta, pode errar — a ideia é sentir o problema. A teoria vem logo abaixo.
Dado um array nums ordenado em ordem crescente e um target, retorne o índice de target. Se não existir, retorne -1. Espera-se O(log n).
Exemplo: nums = [-1, 0, 3, 5, 9, 12], target = 9 → 4. target = 2 → -1.
Tentou? A solução "óbvia" é percorrer o array do começo ao fim — O(n). Ela funciona, mas ignora a informação mais valiosa do enunciado: o array está ordenado. A teoria abaixo mostra como a ordem derruba isso para O(log n).
A teoria: aproveitar a ordem
Num array ordenado, o valor do meio te diz muito. Se você procura target e o
meio é menor que ele, então target — se existir — só pode estar à
direita do meio (tudo à esquerda é ainda menor). Você acabou de descartar
metade do array sem olhar. Simétrico se o meio for maior.
left = 0, right = n - 1
enquanto left <= right:
mid = (left + right) // 2
se nums[mid] == target → achou
se nums[mid] < target → o alvo está à direita: left = mid + 1
se nums[mid] > target → o alvo está à esquerda: right = mid - 1
não achou → -1
Acompanhe o intervalo ativo [left..right] encolhendo pela metade a cada
passo, com mid no centro:
Por que é O(log n)? (a justificativa completa)
A pergunta-chave: quantas vezes dá para dividir n por 2 até sobrar 1 elemento? Essa é a definição de log₂(n):
- n = 8 → 4 → 2 → 1: 3 passos (log₂ 8 = 3)
- n = 1.000.000 → ... → 1: ~20 passos (2²⁰ ≈ 1 milhão)
Cada iteração do laço descarta metade do espaço restante e faz só trabalho O(1) (uma comparação, ajustar um ponteiro). Como o número de iterações é log₂(n), o total é O(log n) de tempo e O(1) de espaço. Não é "mais ou menos rápido" — é exponencialmente melhor que a busca linear.
| Solução | Tempo | Espaço | Exige |
|---|---|---|---|
| Busca linear | O(n) | O(1) | nada |
| Busca binária | O(log n) | O(1) | array ordenado |
A armadilha clássica: os detalhes das fronteiras
Busca binária é fácil de entender e fácil de errar nos detalhes. Três pontos que derrubam muita gente:
left <= rightouleft < right? Comright = n-1(índice válido), use<=— senão você não checa o último elemento quandoleft == right.mid + 1/mid - 1? Comonums[mid]já foi testado, exclua-o do próximo intervalo. Esquecer o±1causa loop infinito.- Overflow do
mid? Em linguagens com inteiro fixo,(left + right)pode estourar;left + (right - left) // 2evita isso. (Em Python/JS do curso não é problema, mas é bom saber para entrevistas em Java/C++.)
Edite o código e force os erros (troque mid + 1 por mid) para ver o loop
infinito ser interrompido pelo limite de passos:
Busca binária é mais que "achar um valor"
O verdadeiro poder vem quando você percebe que busca binária funciona em qualquer espaço monótono — onde existe uma fronteira "antes dela não, a partir dela sim". Procurar o primeiro elemento ≥ x, o último ≤ x, ou até "a menor velocidade que dá conta da tarefa" (busca binária na resposta) — tudo é busca binária com a mesma espinha. Você verá isso na síntese e na prova.
🧠 Quiz de fixação
0/41. Qual informação do enunciado torna a busca binária possível, e que a busca linear ignora?
2. Por que a busca binária é O(log n)?
3. Esquecer de usar mid+1 / mid-1 (e manter left=mid, por exemplo) costuma causar o quê?
4. 'Encontre o primeiro elemento ≥ x num array ordenado.' Busca binária serve?
Resumo
- Busca binária precisa de ordem; olha o meio e descarta metade por passo.
- O(log n) porque n se divide por 2 até chegar a 1 (log₂ n passos), cada um O(1).
- Cuidado com fronteiras:
<=,mid ± 1, overflow domid. - Generaliza para fronteiras e "busca na resposta" — qualquer espaço monótono.
Próxima aula: e quando o array ordenado foi girado? A busca binária modificada.