Busca Binária no Espaço de Respostas
Trate um intervalo contínuo de respostas como espaço de busca para resolver problemas como minimum-time-to-complete-jobs e capacity-to-ship-packages.
Busca Binária no Espaço de Respostas é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 4 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
Busca binária no espaço de respostas
A maioria das pessoas conhece a busca binária para encontrar um valor em um vetor ordenado. Mas a busca binária é ainda mais poderosa quando aplicada ao espaço de respostas possíveis. Em vez de buscar em um vetor, você busca em um intervalo numérico — por exemplo, 'qual é o número mínimo de dias para enviar todos os pacotes?' — e usa uma função de verificação para decidir se uma resposta candidata é viável.
Essa técnica transforma muitos problemas de otimização de O(n²) ou pior em O(n log(max_answer)).
O modelo do espaço de respostas
O modelo tem três componentes. Primeiro, defina o intervalo de busca [lo, hi] que englobe todas as respostas válidas. Segundo, escreva uma verificação de viabilidade can_achieve(mid) que retorne Verdadeiro se o valor no meio for alcançável. Terceiro, faça uma busca binária em [lo, hi]: se can_achieve(mid), aproxime-se de uma resposta menor (ou maior); caso contrário, avance na outra direção.
A propriedade fundamental é que a função de viabilidade deve ser monótona — assim que uma resposta for viável, todos os valores posteriores também serão viáveis (ou todos os anteriores serão inviáveis).
# Generic template
def answer_space_search(lo, hi, is_feasible):
result = hi # or lo, depending on direction
while lo <= hi:
mid = lo + (hi - lo) // 2
if is_feasible(mid):
result = mid
hi = mid - 1 # try to minimise further
else:
lo = mid + 1
return resultExemplo: Capacidade de Envio de Pacotes
LeetCode 1011 'Capacidade de Envio de Pacotes em D Dias': dada uma lista de pesos e D dias, encontre a capacidade mínima de envio necessária para transportar todos os pacotes na ordem indicada dentro de D dias. A resposta está em [max(weights), sum(weights)]. Uma capacidade é viável se uma simulação gulosa conseguir acomodar todos os pacotes dentro de D dias. A busca binária no intervalo de capacidades produz tempo O(n log(soma)).
def shipWithinDays(weights, days):
def can_ship(capacity):
needed_days, current_load = 1, 0
for w in weights:
if current_load + w > capacity:
needed_days += 1
current_load = 0
current_load += w
return needed_days <= days
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = lo + (hi - lo) // 2
if can_ship(mid):
hi = mid # feasible, try smaller
else:
lo = mid + 1 # not feasible, need more capacity
return lo
print(shipWithinDays([1,2,3,4,5,6,7,8,9,10], 5)) # 15
print(shipWithinDays([3,2,2,4,1,4], 3)) # 6Exemplo: Koko Comendo Bananas
LeetCode 875 'Koko Comendo Bananas': Koko consegue comer K bananas por hora; ela quer terminar H montes em exatamente H horas, minimizando K. O intervalo de busca é [1, max(piles)]. A verificação é: à taxa K, o total de horas = soma(ceil(pilha/K)), que deve ser <= H. Fazemos uma busca binária pelo menor K que satisfaça essa condição.
import math
def minEatingSpeed(piles, h):
def can_finish(k):
return sum(math.ceil(p / k) for p in piles) <= h
lo, hi = 1, max(piles)
while lo < hi:
mid = lo + (hi - lo) // 2
if can_finish(mid):
hi = mid # feasible, try lower speed
else:
lo = mid + 1 # too slow
return lo
print(minEatingSpeed([3,6,7,11], 8)) # 4
print(minEatingSpeed([30,11,23,4,20], 5)) # 30Exemplo: Número Mínimo de Dias para Fazer Buquês
LeetCode 1482 'Número Mínimo de Dias para Fazer m Buquês': você precisa de m buquês, cada um formado por k flores consecutivas que já floresceram. A flor i floresce no dia bloomDay[i]. Faça uma busca binária pelo dia: o intervalo é [1, max(bloomDay)]. A verificação de viabilidade conta as flores consecutivas que já floresceram e verifica se é possível formar m buquês. Propriedade monótona: se o dia d funciona, o dia d+1 também funciona.
def minDays(bloomDay, m, k):
if m * k > len(bloomDay):
return -1 # impossible
def can_make(day):
bouquets = consecutive = 0
for bd in bloomDay:
if bd <= day:
consecutive += 1
if consecutive == k:
bouquets += 1
consecutive = 0
else:
consecutive = 0
return bouquets >= m
lo, hi = 1, max(bloomDay)
while lo < hi:
mid = lo + (hi - lo) // 2
if can_make(mid):
hi = mid
else:
lo = mid + 1
return lo
print(minDays([1,10,3,10,2], 3, 1)) # 3
print(minDays([1,10,3,10,2], 3, 2)) # -1Identificando o Intervalo de Busca
Escolher o intervalo [lo, hi] correto é fundamental. lo deve ser a menor resposta possível (por exemplo, o menor elemento, 1 ou 0), e hi deve ser a maior resposta possível (por exemplo, a soma de todos os elementos, o maior elemento ou n). Definir hi como um valor pequeno demais faz com que respostas válidas sejam ignoradas; defini-lo como um valor grande demais não causa problema, pois a busca binária ainda convergirá em O(log(hi - lo)) etapas.
# Choosing lo and hi for common problems:
# Capacity to ship: lo=max(weights), hi=sum(weights)
# Koko eating: lo=1, hi=max(piles)
# Square root: lo=1, hi=x
# Allocate books: lo=max(pages), hi=sum(pages)
def isqrt_bs(x):
if x < 2:
return x
lo, hi = 1, x
while lo < hi:
mid = lo + (hi - lo) // 2
if mid * mid <= x:
lo = mid + 1
else:
hi = mid
return lo - 1
for n in [0, 1, 4, 8, 9, 15, 16]:
print(f'isqrt({n}) = {isqrt_bs(n)}')Maximizar ou Minimizar: a Direção Importa
A busca binária no espaço de respostas tem duas modalidades. Minimizar a resposta: quando a verificação for aprovada, tente valores menores (hi = mid); quando falhar, tente valores maiores (lo = mid + 1). Maximizar a resposta: quando a verificação for aprovada, tente valores maiores (lo = mid + 1, salvando mid como candidato); quando falhar, tente valores menores (hi = mid - 1). Antes de programar, esclareça sempre em qual direção está fazendo a busca.
# Maximise: largest x such that f(x) is feasible
def max_feasible(lo, hi, is_feasible):
result = lo - 1 # sentinel: no feasible answer found
while lo <= hi:
mid = lo + (hi - lo) // 2
if is_feasible(mid):
result = mid
lo = mid + 1 # try larger
else:
hi = mid - 1
return result
# Example: largest k such that k^2 <= 50
print(max_feasible(1, 50, lambda k: k * k <= 50)) # 7Alocar o Mínimo de Páginas (Problema Clássico)
Dado um conjunto de n livros e k estudantes, distribua os livros de forma contígua para que o estudante que leia mais páginas leia o menor número possível. Faça uma busca binária pela resposta (o menor máximo possível). A verificação de viabilidade atribui os livros aos estudantes de forma gulosa: quando adicionar um livro ultrapassaria o máximo atual, atribua-o a um novo estudante. Se forem necessários <= k estudantes, esse máximo é possível.
def allocate_min_pages(pages, k):
if k > len(pages):
return -1
def is_feasible(max_pages):
students, current = 1, 0
for p in pages:
if p > max_pages:
return False # single book exceeds limit
if current + p > max_pages:
students += 1
current = 0
current += p
return students <= k
lo, hi = max(pages), sum(pages)
while lo < hi:
mid = lo + (hi - lo) // 2
if is_feasible(mid):
hi = mid
else:
lo = mid + 1
return lo
print(allocate_min_pages([12, 34, 67, 90], 2)) # 113
print(allocate_min_pages([10, 20, 30, 40], 2)) # 60Análise de Complexidade da Busca no Espaço de Respostas
A complexidade de tempo é O(n × log(intervalo)), onde n é o custo da verificação de viabilidade (geralmente uma varredura linear) e intervalo = hi - lo (o tamanho do espaço de respostas). Por exemplo, se a soma das páginas for 10⁹ e a verificação de viabilidade for O(n), o tempo total será O(n log 10⁹) ≈ O(30n), muito melhor do que a força bruta O(n²).
A complexidade espacial é O(1) para a própria busca binária, além do espaço utilizado pela verificação de viabilidade.
import math
# Compare brute force vs answer-space binary search
# For sum = 10^9 and n = 10^5:
brute_ops = 10**9 # try every possible answer
bsearch_ops = 10**5 * math.log2(10**9) # n * log(range)
print(f'Brute force: {brute_ops:,.0f} operations')
print(f'Binary search: {bsearch_ops:,.0f} operations')
print(f'Speedup: {brute_ops / bsearch_ops:,.0f}x')k-ésimo Menor em uma Matriz Ordenada
LeetCode 378 'k-ésimo Menor Elemento em uma Matriz Ordenada': cada linha e coluna de uma matriz n×n está ordenada. Faça uma busca binária pelo valor da resposta no intervalo entre o elemento no canto superior esquerdo e o elemento no canto inferior direito da matriz. A verificação de viabilidade conta os elementos <= o valor central usando um ponteiro que começa no canto inferior esquerdo, em O(n). Encontre o menor valor para o qual pelo menos k elementos sejam <= esse valor central.
def kthSmallest(matrix, k):
n = len(matrix)
def count_le(mid):
count, row, col = 0, n - 1, 0
while row >= 0 and col < n:
if matrix[row][col] <= mid:
count += row + 1
col += 1
else:
row -= 1
return count
lo, hi = matrix[0][0], matrix[n-1][n-1]
while lo < hi:
mid = lo + (hi - lo) // 2
if count_le(mid) >= k:
hi = mid
else:
lo = mid + 1
return lo
matrix = [[1,5,9],[10,11,13],[12,13,15]]
print(kthSmallest(matrix, 8)) # 13Reconhecendo Problemas no Espaço de Respostas
Os problemas adequados para a busca binária no espaço de respostas compartilham alguns sinais: a pergunta solicita um valor mínimo ou máximo, a resposta está em um intervalo numérico limitado, e aumentar (ou diminuir) a resposta candidata torna a viabilidade monotonicamente melhor ou pior. Palavras-chave comuns incluem 'máximo mínimo possível', 'no máximo k operações' e 'dentro de d dias'.
Ao identificar esses sinais, defina imediatamente lo e hi, escreva a função de viabilidade e aplique o modelo. Essa abordagem estruturada raramente falha em entrevistas técnicas.
Verificação Rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.
Recapitulação da Lição
Nesta lição, você aprendeu: a busca binária no espaço de respostas se aplica quando uma função de viabilidade é monótona em um intervalo numérico, o modelo pesquisa [lo, hi] e usa uma verificação de alcançabilidade para reduzir o espaço de busca pela metade, e a complexidade total é O(n log(intervalo)), onde n é o custo de uma verificação de viabilidade. A seguir, passaremos para listas encadeadas e a classe Nó.
Perguntas Frequentes
A aula “Busca Binária no Espaço de Respostas” é grátis?
Sim — o texto completo de “Busca Binária no Espaço de Respostas” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Busca Binária no Espaço de Respostas”?
Trate um intervalo contínuo de respostas como espaço de busca para resolver problemas como minimum-time-to-complete-jobs e capacity-to-ship-packages. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 4 de 4.
Quanto tempo leva a aula “Busca Binária no Espaço de Respostas”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Busca Binária Clássica: Esquerda, Direita, Meio
- Busca Binária em Arrays Rotacionados e Não Ordenados
- Limite Inferior e Limite Superior
- Busca Binária no Espaço de Respostas