Ricerca binaria sulla risposta
Ipotizzare il risultato e verificarne la fattibilità
Ricerca binaria sulla risposta è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 4 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.
Formuli un'ipotesi, poi la verifichi
A volte non può calcolare direttamente la risposta, ma può verificare un'ipotesi. La ricerca binaria sulla risposta trasforma un'ottimizzazione difficile in una verifica semplice.
# guess X, ask: is X feasible?La proprietà magica
Funziona quando la fattibilità è monotona: se un valore funziona, funziona anche ogni valore maggiore (o minore). È questo ordinamento a costituire l'oggetto della ricerca.
# feasible(X) true => feasible(X+1) trueDelimiti l'intervallo della risposta
Individui la risposta minima e massima possibili come low e high. Per la capacità minima, low è un singolo elemento e high è la somma totale.
low, high = max(weights), sum(weights)Scriva il controllo di fattibilità
Il cuore del metodo è una funzione can(X) che restituisce true se l'ipotesi X è realizzabile. Di solito viene eseguita in tempo lineare.
def can(cap):
# simulate and return True/False
...Esempio: spedire in D giorni
Data la capacità giornaliera cap, riempia avidamente i giorni e li conti. can(cap) è true quando il numero di giorni rimane entro il 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 <= DCerchi la capacità minima
Sta cercando il valore minimo di cap che supera il controllo. Si tratta di una ricerca del primo true sulle capacità, quindi riutilizzi il modello high = mid.
while low < high:
mid = (low + high) // 2Mantenga la metà fattibile
Se can(mid) è true, potrebbe funzionare anche una capacità inferiore, quindi imposti high = mid. Altrimenti alzi il limite inferiore con low = mid + 1.
if can(mid):
high = mid
else:
low = mid + 1Tenga conto del tempo disponibile
Il costo totale è O(check x log range). Un controllo lineare su un intervallo ampio un miliardo richiede solo circa 30 verifiche, abbastanza rapidamente anche con limiti rigidi.
# log2(1e9) is about 30 iterationsMassimizzi invece di minimizzare
Per trovare il valore fattibile massimo, inverta la logica: cerchi l'ultimo true. Aumenti low quando il valore è fattibile e riduca high quando non lo è.
if can(mid):
low = mid
else:
high = mid - 1Risposte con valori reali
Per le risposte in virgola mobile, esegua il ciclo per un numero fisso di volte, ad esempio 100, invece di usare mid intero. Ogni iterazione dimezza l'intervallo e raggiunge rapidamente una precisione finissima.
for _ in range(100):
mid = (low + high) / 2Riconosca lo schema
Espressioni come minimo dei massimi, massimo dei minimi o il più piccolo k che funziona sono segnali che indicano di cercare la risposta con la ricerca binaria. Alleni il suo occhio a riconoscerle.
# 'minimize the maximum' => search answerControllo rapido
Decida quando è applicabile la ricerca binaria sulla risposta.
Riepilogo: cerchi la risposta
Ora sa delimitare la risposta, scrivere un controllo di fattibilità e cercare il minimo o il massimo con la ricerca binaria. I problemi difficili diventano un processo di ipotesi e verifica. 🏆
Domande Frequenti
La lezione «Ricerca binaria sulla risposta» è gratuita?
Sì — il testo completo di «Ricerca binaria sulla risposta» è 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 «Ricerca binaria sulla risposta»?
Ipotizzare il risultato e verificarne la fattibilità 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 4 di 4.
Quanto tempo richiede la lezione «Ricerca binaria sulla risposta»?
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