Ricerca binaria nello spazio delle risposte
Tratti un intervallo continuo di risposte come spazio di ricerca per risolvere problemi come minimum-time-to-complete-jobs e capacity-to-ship-packages
Ricerca binaria nello spazio delle risposte è una lezione DSA Interview Prep 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 DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.
Ricerca binaria nello spazio delle soluzioni
La maggior parte delle persone conosce la ricerca binaria per trovare un valore in un array ordinato. Tuttavia, la ricerca binaria è ancora più potente quando viene applicata allo spazio delle possibili risposte. Invece di cercare in un array, si cerca in un intervallo numerico, ad esempio per rispondere alla domanda «qual è il numero minimo di giorni necessari per spedire tutti i pacchi?», usando una funzione di verifica per stabilire se una risposta candidata è fattibile.
Questa tecnica trasforma molti problemi di ottimizzazione da O(n²) o peggio in O(n log(max_answer)).
Il modello dello spazio delle soluzioni
Il modello comprende tre componenti. Per prima cosa, definisca l'intervallo di ricerca [lo, hi] che contiene tutte le risposte valide. In secondo luogo, scriva una verifica di fattibilità can_achieve(mid) che restituisca True se il valore mid è raggiungibile. Infine, esegua la ricerca binaria nell'intervallo [lo, hi]: se can_achieve(mid) restituisce True, si sposti verso una risposta più piccola (o più grande); altrimenti proceda nella direzione opposta.
La proprietà fondamentale è che la funzione di fattibilità deve essere monotona: una volta che una risposta è fattibile, lo sono anche tutti i valori successivi (oppure tutti quelli precedenti non sono fattibili).
# 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 resultEsempio: capacità di spedizione dei pacchi
LeetCode 1011 «Capacità necessaria per spedire pacchi entro D giorni»: data una lista di pesi e D giorni, trovare la capacità minima necessaria per spedire tutti i pacchi nell'ordine indicato entro D giorni. La risposta si trova in [max(weights), sum(weights)]. Una capacità è fattibile se una simulazione greedy consente di spedire tutti i pacchi entro D giorni. La ricerca binaria sull'intervallo delle capacità richiede tempo O(n log(sum)).
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)) # 6Esempio: Koko mangia banane
LeetCode 875 «Koko mangia banane»: Koko può mangiare K banane all'ora; vuole finire H mucchi in esattamente H ore, minimizzando K. L'intervallo di ricerca è [1, max(piles)]. Al ritmo K, il totale delle ore è sum(ceil(pile/K)) e deve essere <= H. Si esegue una ricerca binaria per trovare il valore minimo di K che soddisfa questa condizione.
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)) # 30Esempio: numero minimo di giorni per creare bouquet
LeetCode 1482 «Numero minimo di giorni per creare m bouquet»: sono necessari m bouquet, ciascuno composto da k fiori consecutivi già sbocciati. Il fiore i sboccia nel giorno bloomDay[i]. Si esegue una ricerca binaria sul giorno: l'intervallo è [1, max(bloomDay)]. Il controllo di fattibilità conta i fiori consecutivi già sbocciati e verifica se è possibile formare m bouquet. Proprietà di monotonia: se il giorno d funziona, anche il giorno d+1 funziona.
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)) # -1Identificare l'intervallo di ricerca
Scegliere l'intervallo [lo, hi] corretto è fondamentale. lo dovrebbe essere la risposta minima possibile (ad esempio, l'elemento minimo, 1 o 0), mentre hi dovrebbe essere la risposta massima possibile (ad esempio, la somma di tutti gli elementi, l'elemento massimo o n). Impostare hi su un valore troppo piccolo fa perdere risposte valide; impostarlo su un valore troppo grande non è un problema, perché la ricerca binaria convergerà comunque in O(log(hi - lo)) passaggi.
# 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)}')Massimizzare o minimizzare: la direzione è importante
La ricerca binaria nello spazio delle risposte ha due varianti. Minimizzare la risposta: quando il controllo ha esito positivo, si prova un valore più piccolo (hi = mid); quando ha esito negativo, si prova un valore più grande (lo = mid + 1). Massimizzare la risposta: quando il controllo ha esito positivo, si prova un valore più grande (lo = mid + 1, conservando mid come candidato); quando ha esito negativo, si prova un valore più piccolo (hi = mid - 1). Prima di scrivere il codice, è sempre necessario chiarire in quale direzione si sta cercando.
# 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)) # 7Allocazione del numero minimo di pagine (problema classico)
Dati n libri con pages[] e k studenti, assegnare i libri in modo contiguo affinché lo studente che legge più pagine ne legga il minor numero possibile. Si esegue una ricerca binaria sulla risposta (il minimo possibile del massimo). Il controllo di fattibilità assegna avidamente i libri agli studenti: quando aggiungere un libro supererebbe il massimo corrente, lo si assegna a un nuovo studente. Se il numero di studenti necessari è <= k, quel valore massimo è raggiungibile.
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)) # 60Analisi della complessità della ricerca nello spazio delle risposte
La complessità temporale è O(n × log(range)), dove n è il costo del controllo di fattibilità (di solito una scansione lineare) e range = hi - lo è l'ampiezza dello spazio delle risposte. Ad esempio, se la somma delle pagine è 10⁹ e il controllo di fattibilità è O(n), il tempo totale è O(n log 10⁹) ≈ O(30n), molto migliore della forza bruta O(n²).
La complessità spaziale è O(1) per la ricerca binaria in sé, oltre allo spazio utilizzato dal controllo di fattibilità.
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')Il k-esimo elemento più piccolo in una matrice ordinata
LeetCode 378 «K-esimo elemento più piccolo in una matrice ordinata»: ogni riga e ogni colonna di una matrice n×n è ordinata. Si esegue una ricerca binaria sul valore della risposta nell'intervallo [matrix[0][0], matrix[n-1][n-1]]. Il controllo di fattibilità conta gli elementi <= mid usando un puntatore che parte dall'angolo inferiore sinistro, con complessità O(n). Si trova il valore minimo per cui almeno k elementi sono <= mid.
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)) # 13Riconoscere i problemi nello spazio delle risposte
I problemi adatti alla ricerca binaria nello spazio delle risposte presentano alcuni segnali ricorrenti: la domanda chiede un valore minimo o massimo, la risposta si trova in un intervallo numerico limitato e aumentare (o diminuire) la risposta candidata rende la fattibilità progressivamente migliore o peggiore. Tra le parole chiave tipiche figurano «minimo massimo possibile», «al massimo k operazioni» e «entro d giorni».
Quando si individuano questi segnali, occorre definire subito lo e hi, scrivere la funzione di fattibilità e applicare il modello. Questo approccio strutturato raramente fallisce nei colloqui tecnici.
Controllo rapido
Verifichi la comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep presentati in questa lezione.
Riepilogo della lezione
In questa lezione ha appreso che: la ricerca binaria nello spazio delle risposte si applica quando una funzione di fattibilità è monotona su un intervallo numerico, il modello cerca in [lo, hi] e usa un controllo can_achieve per dimezzare lo spazio di ricerca e la complessità totale è O(n log(range)), dove n è il costo di un singolo controllo di fattibilità. Nella prossima lezione si passerà alle liste concatenate e alla classe Node.
Domande Frequenti
La lezione «Ricerca binaria nello spazio delle risposte» è gratuita?
Sì — il testo completo di «Ricerca binaria nello spazio delle risposte» è 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 DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Ricerca binaria nello spazio delle risposte»?
Tratti un intervallo continuo di risposte come spazio di ricerca per risolvere problemi come minimum-time-to-complete-jobs e capacity-to-ship-packages Eserciti DSA Interview Prep 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 DSA Interview Prep?
Non è richiesta alcuna esperienza precedente. DSA Interview Prep 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 nello spazio delle risposte»?
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 DSA Interview Prep?
Sì. Ogni lezione DSA Interview Prep 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: sinistra, destra, centro
- Ricerca binaria su array ruotati e non ordinati
- Limite inferiore e limite superiore
- Ricerca binaria nello spazio delle risposte