Busca Binária na Resposta
Adivinhe o resultado e verifique a viabilidade.
Busca Binária na Resposta é 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.
Adivinhe e depois verifique
Às vezes não é possível calcular a resposta diretamente, mas é possível verificar uma hipótese. Fazer busca binária na resposta transforma uma otimização difícil em uma verificação simples.
# guess X, ask: is X feasible?A propriedade mágica
Isso funciona quando a viabilidade é monotônica: se um valor funciona, todo valor maior (ou menor) também funciona. É essa ordenação que você busca.
# feasible(X) true => feasible(X+1) trueDelimite o intervalo da resposta
Identifique as menores e maiores respostas possíveis como low e high. Para a capacidade mínima, low é um item e high é a soma total.
low, high = max(weights), sum(weights)Escreva a verificação de viabilidade
O coração do método é uma função can(X) que retorna verdadeiro se a hipótese X for alcançável. Ela geralmente é executada em tempo linear.
def can(cap):
# simulate and return True/False
...Exemplo: envio em D dias
Dada a capacidade diária cap, preencha os dias de forma gulosa e conte-os. can(cap) será verdadeiro quando a quantidade de dias permanecer dentro do limite D.
def can(cap):
days, load = 1, 0
for w in weights:
if load + w > cap:
days += 1; load = 0
load += w
return days <= DBusque a capacidade mínima
Você quer a menor cap que seja aprovada. Esta é uma busca do primeiro verdadeiro entre as capacidades; portanto, reutilize o modelo high = mid.
while low < high:
mid = (low + high) // 2Mantenha a metade viável
Se can(mid) for verdadeiro, uma capacidade menor ainda poderá funcionar; portanto, defina high = mid. Caso contrário, aumente o limite inferior com low = mid + 1.
if can(mid):
high = mid
else:
low = mid + 1Tenha em mente o limite de tempo
O custo total é O(custo da verificação x logaritmo do intervalo). Uma verificação linear em um intervalo de um bilhão de posições exige apenas cerca de 30 verificações, rápido o suficiente mesmo para limites rigorosos.
# log2(1e9) is about 30 iterationsMaximize em vez de minimizar
Para encontrar o maior valor viável, inverta a lógica: busque o último verdadeiro. Aumente low quando for viável e reduza high quando não for.
if can(mid):
low = mid
else:
high = mid - 1Respostas de valores reais
Para respostas com ponto flutuante, repita um número fixo de vezes, como 100, em vez de usar um mid inteiro. A cada rodada, o intervalo é reduzido pela metade, alcançando uma precisão minúscula rapidamente.
for _ in range(100):
mid = (low + high) / 2Identifique o padrão
Expressões como menor dos maiores, maior dos menores ou menor k que funciona são sinais para fazer busca binária na resposta. Treine seu olhar para reconhecê-las.
# 'minimize the maximum' => search answerVerificação rápida
Decida quando a busca binária na resposta se aplica.
Recapitulação: busque a resposta
Agora você pode delimitar a resposta, escrever uma verificação de viabilidade e fazer busca binária pelo mínimo ou pelo máximo. Problemas difíceis se tornam uma questão de supor e verificar. 🏆
Perguntas Frequentes
A aula “Busca Binária na Resposta” é grátis?
Sim — o texto completo de “Busca Binária na Resposta” é 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 na Resposta”?
Adivinhe o resultado e verifique a viabilidade. 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 na Resposta”?
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 sem Bugs
- bisect_left e bisect_right
- Primeiro True: Busca Binária por Predicado
- Busca Binária na Resposta