Mundo Tech Software SchoolMTSS
0x50Lição 6 de 13

Corte o espaço de busca pela metade com busca binária

Busque em dados ordenados - ou em qualquer condição monotônica - em O(log n).

20 min Questionário com 5 perguntas 1 exercício de código
Ao final desta lição, você saberá
  • Escrever uma busca binária sem bugs.
  • Encontrar a primeira posição em que uma condição fica verdadeira.
  • Reconhecer a busca binária sobre respostas, não só sobre arrays.

A busca binária corta repetidamente pela metade um espaço de busca ordenado: compare o elemento do meio e descarte a metade que não pode conter a resposta. Um milhão de itens leva cerca de 20 passos. Além de encontrar um valor num array ordenado, ela resolve qualquer problema em que uma condição de sim/não muda exatamente uma vez - “a primeira versão com defeito”, “a menor capacidade que entrega todos os pacotes em D dias”.

Um modelo que evita bugs de off-by-one

Use um intervalo semiaberto [low, high) e encontre o primeiro índice em que uma condição é verdadeira:

  1. Comece com low = 0, high = len(nums).
  2. Enquanto low < high: pegue mid = (low + high) // 2.
  3. Se a condição vale em mid, a resposta está em mid ou à esquerda dele: high = mid. Caso contrário, está à direita: low = mid + 1.
  4. Quando o laço termina, low é o primeiro índice em que a condição vale (ou len(nums), se nenhum valer).
solution.py
1def first_at_least(nums, target):
2    low, high = 0, len(nums)
3    while low < high:
4        mid = (low + high) // 2
5        if nums[mid] >= target:
6            high = mid
7        else:
8            low = mid + 1
9    return low
10
11nums = [1, 3, 5, 7, 9]
12print(first_at_least(nums, 5), first_at_least(nums, 6), first_at_least(nums, 10))
Saída
2 3 5

Essa busca de “limite inferior” responde várias perguntas de uma vez: se o alvo existe (low < len(nums) and nums[low] == target), onde inseri-lo para manter a lista ordenada e quantos elementos são menores que ele. O bisect.bisect_left do Python implementa exatamente isso.

Principais conclusões

  • A busca binária precisa de dados ordenados ou de uma condição que muda uma única vez.

  • Use sempre o mesmo modelo; a versão semiaberta encontra a primeira posição verdadeira.

  • Você pode fazer busca binária sobre as respostas possíveis, não só sobre índices.

Quiz da aula

5 perguntas · aprovação com 4 acertos · até 50 XP

Ao passar, você conclui a aula e mantém sua sequência. As perguntas erradas voltarão em sessões de revisão.

Pratique: resolva problemas de entrevistas técnicas

Resolva um problema clássico de entrevista em Python e execute-o com casos de teste. Busque a complexidade ideal e depois confira os casos extremos. Os exercícios rodam localmente no navegador.

Exercício 1

Encontre a posição de inserção

+25 XP

Leia uma linha de inteiros distintos em ordem crescente e depois um alvo. Imprima o índice do alvo, se ele estiver presente; caso contrário, o índice em que ele seria inserido para manter a lista ordenada. Use busca binária.

  • Alvo presente
  • Inserir no meio
  • Inserir no fim
  • Inserir no início
main.py
Carregando editor…

O Python é executado em um ambiente isolado no navegador, com limite de 60 segundos. O runtime é carregado pelo CDN do Pyodide; seu código permanece neste navegador.

Dúvidas sobre esta lição

Travou em algum ponto? Pergunte. Descobriu algo? Compartilhe. Explicar também é uma ótima forma de aprender.

Carregando publicações…