Binary Search
Ti viene fornito un elenco di numeri interi nums ordinati in ordine crescente, senza valori ripetuti, e un numero intero target. Restituisci l'indice di target in nums, contando da 0, oppure -1 se non è nell'elenco. Punta a un tempo di esecuzione di O(log n), il che significa che non puoi permetterti di esaminare ogni elemento.
Funzione
- numsinteger-array
- l'elenco ordinato di interi distinti
- targetinteger
- il valore da cercare
- Restituisceinteger
- l'indice di target in nums, oppure -1 se non è presente
Vincoli
1 ≤ nums.length ≤ 104-104 ≤ nums[i], target ≤ 104numsè ordinato in ordine strettamente crescente, quindi ogni valore compare una sola volta.
Esempi
- Input
- nums = [-7, -2, 0, 4, 9, 15, 23]target = 9
- Output
- 4
- Spiegazione
nums[4]è 9. La ricerca controlla l'indice 3 (valore 4, troppo piccolo), poi l'indice 5 (valore 15, troppo grande), quindi l'indice 4, dove trova 9.
- Input
- nums = [1, 3, 5, 8, 13, 21]target = 10
- Output
- -1
- Spiegazione
- 10 si troverebbe tra 8 e 13, e nessuno dei due è 10, quindi non è nell’elenco. L’intervallo di ricerca si restringe finché
losuperahi, e la funzione restituisce-1.
+15 test nascosti all’invio
Per approfondire
Se nums potesse contenere valori ripetuti, come restituiresti il primo indice di target, sempre in O(log n)?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
La lista è ordinata. Se confronti
targetcon un elemento al centro, cosa ti dice questo su tutti gli elementi che si trovano da un lato?Se
nums[mid] < target, alloranums[mid]e tutto ciò che si trova alla sua sinistra sono troppo piccoli, quinditargetpuò trovarsi solo a destra. Un confronto elimina metà dei candidati.Mantieni due indici,
loehi, attorno alla parte della lista che potrebbe ancora conteneretarget. Confronta con l’elemento centrale, spostaloohioltre di esso e fermati quando trovitargetolosuperahi.
Soluzione
Esaminare gli elementi uno per uno consente di trovare target, ma ignora il fatto che rende interessante il problema: la lista è ordinata. Un singolo confronto con l’elemento centrale ti dice quale metà può ancora contenere target, così puoi scartare metà dei candidati a ogni passaggio. Una lista di 10^4 elementi richiede quindi al massimo 14 confronti anziché 10000.
Scansiona da sinistra a destra
Intuizione
Controlla ogni indice nell’ordine e restituisci il primo il cui valore è uguale a target. Se il ciclo termina senza trovare corrispondenze, target non è nell’elenco, quindi restituisci -1. Ogni elemento viene confrontato una volta, il che rende la risposta corretta per qualsiasi elenco, ordinato o meno.
È proprio questa generalità il problema. Un elenco di 10^4 elementi richiede fino a 10000 confronti, e il lavoro cresce proporzionalmente a n. La scansione non sfrutta il fatto che nums sia ordinato, quindi non raggiunge il limite O(log n) richiesto dall’esercizio. Potresti fermarti non appena un valore supera target, ma nel caso peggiore leggeresti comunque l’intero elenco.
Algoritmo
- Per ogni indice
ida 0 an-1, confrontanums[i]contarget. - Se sono uguali, restituisci
i. - Dopo il ciclo, restituisci
-1.
def search(nums, target):
for i, value in enumerate(nums):
if value == target:
return i
return -1Ricerca binaria con due indici
Intuizione
Mantieni due indici, lo e hi, con una promessa: se target è nell’elenco, il suo indice si trova tra lo e hi, estremi inclusi. All’inizio l’intervallo comprende l’intero elenco, da 0 a n-1. Guarda l’indice centrale mid. Se nums[mid] è uguale a target, hai finito. Se è minore, allora, poiché l’elenco è ordinato, anche tutti gli elementi fino a mid sono minori, quindi sposta lo a mid + 1. Se è maggiore, sposta hi a mid - 1. La promessa rimane valida dopo ciascuno dei due spostamenti.
Segui il primo esempio, [-7, -2, 0, 4, 9, 15, 23] con target = 9. L’intervallo da 0 a 6 ha come indice centrale 3, con valore 4, troppo piccolo, quindi l’intervallo diventa da 4 a 6. Il suo indice centrale è 5, con valore 15, troppo grande, quindi l’intervallo diventa da 4 a 4. L’indice 4 contiene 9: restituisci 4.
Se target non è presente, l’intervallo continua a restringersi finché lo supera hi. A quel punto l’intervallo è vuoto, la promessa indica che target non si trova da nessuna parte e restituisci -1. Ogni passaggio dimezza l’intervallo, quindi il ciclo viene eseguito al massimo circa log2(n) + 1 volte: 14 passaggi per 10^4 elementi. Ti bastano due indici come memoria aggiuntiva.
Algoritmo
- Imposta
lo = 0ehi = n-1. - Mentre
lo ≤ hi, calcolamid = lo + (hi - lo) / 2. - Se
nums[mid]è uguale atarget, restituiscimid. - Se
nums[mid] < target, impostalo = mid + 1; altrimenti impostahi = mid - 1. - Quando il ciclo termina, restituisci
-1.
def search(nums, target):
lo, hi = 0, len(nums) - 1 # target, if present, sits in nums[lo..hi]
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1 # nums[mid] and everything left of it is too small
else:
hi = mid - 1 # nums[mid] and everything right of it is too big
return -1
Trappole e casi limite
La ricerca binaria è breve e quasi tutti i bug sono errori di una posizione ai limiti dell’intervallo.
- Usare un ciclo con
lo < hiquandohiparte dall’ultimo indice. Il ciclo si interrompe mentre un candidato non è ancora stato controllato, quindinums = [5]contarget = 5restituisce-1. Con un intervallo inclusivo, usa il ciclo finchélo ≤ hi. - Passare a
lo = midohi = midcon un intervallo inclusivo. Quandoloehisono adiacenti,midè uguale aloe l’intervallo non si restringe mai: si crea un ciclo infinito. Hai già controllatonums[mid], quindi superalo conmid + 1omid - 1. - Calcolare
(lo + hi) / 2con un intero a larghezza fissa. La somma va in overflow quando gli indici superano circa10^9. I limiti qui sono molto inferiori, malo + (hi - lo) / 2è l’abitudine più sicura. - Restituire
loquandotargetnon è presente. Dopo il ciclo,loè il punto di inserimento, che è un indice valido, non-1. - Dimenticare lo spostamento in Lua e R. Le loro liste iniziano da 1, quindi l’indice da restituire è la posizione meno 1.
Domande frequenti4
Qual è la complessità temporale della ricerca binaria?
O(log n). Ogni confronto dimezza l'intervallo in cui può ancora trovarsi l'elemento cercato, quindi dopo k passaggi rimangono al massimo n / 2^k candidati. Una lista di 10^4 elementi richiede al massimo 14 confronti, mentre una lista di 10^9 elementi ne richiede al massimo 30. La versione iterativa usa O(1) spazio aggiuntivo.
Perché la ricerca binaria ha bisogno di un array ordinato?
Il passaggio che scarta metà dell’elenco si basa sull’ordinamento. Quando nums[mid] < target, l’ordinamento garantisce che ogni elemento a sinistra di mid sia anch’esso minore di target, quindi nessuno di essi può corrispondere. In un elenco non ordinato, quel confronto non dice nulla sugli altri elementi e devi controllarli tutti.
La ricerca binaria dovrebbe essere iterativa o ricorsiva?
Entrambi sono corretti ed entrambi vengono eseguiti in tempo O(log n). La versione ricorsiva richiama sé stessa su una metà e usa O(log n) di spazio nello stack; la versione iterativa sposta lo e hi in un ciclo e usa O(1). Di solito chi fa i colloqui si aspetta il ciclo, che evita anche qualsiasi limite di ricorsione.
Come si evita l'overflow nel calcolo dell'indice centrale?
Scrivi mid = lo + (hi - lo) / 2 invece di (lo + hi) / 2. Entrambe le forme restituiscono lo stesso indice, ma la seconda somma prima due indici e, con un intero a 32 bit, la somma va in overflow quando gli indici superano circa 1.07 × 10^9. Python e Ruby hanno interi senza limiti, quindi in quei linguaggi la forma breve è sicura.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def search(nums, target):
# Scrivi il codice quiCaso 1
Caso 2
Input
nums = [-7, -2, 0, 4, 9, 15, 23] target = 9
Atteso
4