Primeiro True: Busca Binária por Predicado
Busque uma fronteira monotônica de sim/não.
Primeiro True: Busca Binária por Predicado é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 3 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 Competitive Programming Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Competitive Programming Academy inclui 4 aulas no total.
Busque um limite de sim ou não
Muitos problemas escondem um predicado monotônico: falso, falso e depois verdadeiro para sempre. A busca binária pode encontrar o primeiro verdadeiro sem um vetor ordenado.
# FFFFTTTT -> find first TO que significa monotônico
Um predicado é monotônico quando, depois que se torna verdadeiro, continua verdadeiro. Essa única propriedade permite buscar o limite com busca binária.
def ok(x):
return x * x >= targetDelimite o espaço de respostas
Escolha um intervalo que certamente contenha o limite. Defina low como o menor candidato e high como um valor em que ok seja certamente verdadeiro.
low, high = 0, 10**9Teste o meio
Obtenha mid e chame ok(mid). O resultado booleano informa qual metade manter, exatamente como ao comparar um valor em uma busca binária comum.
mid = (low + high) // 2
if ok(mid):
...Verdadeiro significa talvez menor
Se ok(mid) for verdadeiro, mid será uma resposta válida, mas uma resposta menor também poderá funcionar. Preserve mid definindo high = mid, não mid - 1.
if ok(mid):
high = midFalso significa ir para cima
Se ok(mid) for falso, o limite estará acima de mid. Descarte mid e tudo abaixo dele com low = mid + 1.
else:
low = mid + 1Repita enquanto low estiver abaixo de high
Use while low < high, não menor ou igual. Os dois ponteiros convergem para o primeiro índice verdadeiro e então o laço para.
while low < high:
mid = (low + high) // 2A resposta é low
Quando o laço termina, low é igual a high e ambos apontam para o valor primeiro verdadeiro. Retorne low como o limite que você procurava.
return low # first x where ok(x)Por que high = mid funciona
Como mid pode ser a resposta, você não deve ignorá-lo. Usar high = mid o mantém no intervalo enquanto ainda o reduz, garantindo progresso.
high = mid # mid stays a candidateExemplo de raiz quadrada inteira
Para encontrar o maior x tal que x*x seja no máximo n, busque o primeiro verdadeiro de x*x > n e depois recue uma posição. O padrão se reutiliza.
def ok(x):
return x * x > n
# answer is found_index - 1Um modelo, muitos problemas
Este modelo de primeiro verdadeiro resolve inúmeras tarefas: menor valor viável, índice mais à esquerda e menor capacidade. Aprenda-o uma vez e reutilize-o em qualquer lugar.
# low<high, ok->high=mid, else low=mid+1Verificação rápida
Identifique o movimento que mantém o candidato vivo.
Recapitulação: primeiro verdadeiro encontrado
Agora você pode transformar um problema em um predicado monotônico e buscar o limite com busca binária. high = mid junto de while low < high é o padrão seguro. 🧭
Perguntas Frequentes
A aula “Primeiro True: Busca Binária por Predicado” é grátis?
Sim — o texto completo de “Primeiro True: Busca Binária por Predicado” é 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 Competitive Programming Academy, atualize para CoddyKit PRO. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que vou aprender em “Primeiro True: Busca Binária por Predicado”?
Busque uma fronteira monotônica de sim/não. Você pratica Competitive Programming Academy 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 Competitive Programming Academy?
Nenhuma experiência prévia é necessária. Competitive Programming Academy 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 3 de 4.
Quanto tempo leva a aula “Primeiro True: Busca Binária por Predicado”?
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 Competitive Programming Academy?
Sim. Cada aula de Competitive Programming Academy 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