Primo True: ricerca binaria sul predicato
Cercare il confine monotono tra sì e no
Primo True: ricerca binaria sul predicato è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Competitive Programming Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Competitive Programming Academy include 4 lezioni in totale.
Cerchi un confine sì/no
Molti problemi nascondono un predicato monotono: false, false, poi sempre true. La ricerca binaria può trovare il primo true senza un array ordinato.
# FFFFTTTT -> find first TChe cosa significa monotono
Un predicato è monotono quando, una volta diventato true, rimane true. È proprio questa proprietà a permettere di cercare il confine con la ricerca binaria.
def ok(x):
return x * x >= targetDefinisca lo spazio delle risposte
Scelga un intervallo che contenga certamente il confine. Imposti low sul candidato più piccolo e high su un valore per cui ok è certamente true.
low, high = 0, 10**9Verifichi il punto centrale
Prenda mid e chiami ok(mid). Il risultato booleano indica quale metà mantenere, esattamente come il confronto con un valore nella ricerca binaria classica.
mid = (low + high) // 2
if ok(mid):
...true significa forse più piccolo
Se ok(mid) è true, mid è una risposta valida, ma potrebbe funzionare anche un valore più piccolo. Mantenga mid impostando high = mid, non mid - 1.
if ok(mid):
high = midfalse significa andare più in alto
Se ok(mid) è false, il confine si trova oltre mid. Elimini mid e tutto ciò che viene prima con low = mid + 1.
else:
low = mid + 1Ripeta finché low è minore di high
Usi while low < high, non una condizione di minore o uguale. I due puntatori convergono sul primo indice true e poi il ciclo termina.
while low < high:
mid = (low + high) // 2La risposta è low
Quando il ciclo termina, low è uguale a high ed entrambi indicano il valore del primo true. Restituisca low come confine che stava cercando.
return low # first x where ok(x)Perché high = mid funziona
Poiché mid può essere la risposta, deve non escluderlo. Usare high = mid lo mantiene nell'intervallo, continuando comunque a ridurlo e garantendo il progresso.
high = mid # mid stays a candidateEsempio: radice quadrata intera
Per trovare il massimo x tale che x*x sia al massimo n, cerchi il primo true di x*x > n, poi torni indietro di uno. Questo schema è riutilizzabile.
def ok(x):
return x * x > n
# answer is found_index - 1Un modello, molti problemi
Questo modello first-true risolve innumerevoli problemi: valore minimo ammissibile, indice più a sinistra, capacità minima. Lo impari una volta e lo riutilizzi ovunque.
# low<high, ok->high=mid, else low=mid+1Controllo rapido
Individui il passaggio che mantiene in gioco il candidato.
Riepilogo: trovato il primo true
Ora sa trasformare un problema in un predicato monotono e cercare il confine con la ricerca binaria. high = mid insieme a while low < high è lo schema sicuro. 🧭
Domande Frequenti
La lezione «Primo True: ricerca binaria sul predicato» è gratuita?
Sì — il testo completo di «Primo True: ricerca binaria sul predicato» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Competitive Programming Academy, passa a CoddyKit PRO. Il corso Competitive Programming Academy include 4 lezioni in totale.
Cosa imparerò in «Primo True: ricerca binaria sul predicato»?
Cercare il confine monotono tra sì e no Eserciti Competitive Programming Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Competitive Programming Academy?
Non è richiesta alcuna esperienza precedente. Competitive Programming Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «Primo True: ricerca binaria sul predicato»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Competitive Programming Academy?
Sì. Ogni lezione Competitive Programming Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Ricerca binaria classica senza bug
- bisect_left e bisect_right
- Primo True: ricerca binaria sul predicato
- Ricerca binaria sulla risposta