Search in Rotated Sorted Array
Un elenco di interi distinti è stato ordinato in ordine crescente e poi ruotato: un certo numero di elementi, eventualmente zero, è stato preso dall’inizio e spostato alla fine nello stesso ordine. Per esempio, ruotando di 4 [2, 5, 8, 11, 15, 19, 23] si ottiene [15, 19, 23, 2, 5, 8, 11]. Ricevi l’elenco ruotato nums e un intero target. Restituisci l’indice di target in nums, contando da 0, oppure -1 se non è presente, in tempo O(log n).
Funzione
- numsinteger-array
- l'elenco ruotato ordinato di numeri interi distinti
- targetinteger
- il valore da cercare
- Restituisceinteger
- l'indice di target in nums, oppure -1 se non è presente
Vincoli
1 ≤ nums.length ≤ 5000-104 ≤ nums[i], target ≤ 104- Tutti i valori in
numssono distinti. numsè una lista crescente ruotata di un certok, con0 ≤ k < nums.length;k = 0la lascia non ruotata.
Esempi
- Input
- nums = [15, 19, 23, 2, 5, 8, 11]target = 5
- Output
- 4
- Spiegazione
- 5 si trova all'indice 4. Il primo elemento centrale, all'indice 3, contiene 2, quindi la metà destra
[2, 5, 8, 11]è quella ordinata e 5 si trova tra 2 e 11. Il successivo elemento centrale, all'indice 5, contiene 8; la parte sinistra ordinata[5, 8]contiene 5, il che porta all'indice 4.
- Input
- nums = [40, 50, 60, 70, 10, 20, 30]target = 65
- Output
- -1
- Spiegazione
- 65 dovrebbe trovarsi tra 60 e 70, ma nessun elemento lo contiene. Il primo elemento centrale, 70 all’indice 3, colloca 65 nella parte sinistra ordinata
[40, 50, 60, 70]. L’intervallo si restringe all’interno di quella sequenza finché non è vuoto, quindi la funzione restituisce-1.
- Input
- nums = [8, 13, 21, 1, 3, 5]target = 13
- Output
- 1
- Spiegazione
- Il primo elemento centrale, indice 2, contiene 21. La parte sinistra
[8, 13, 21]è ordinata e 13 si trova tra 8 e 21, quindi l’intera parte destra viene scartata. La ricerca trova quindi 13 all’indice 1.
+23 test nascosti all’invio
Per approfondire
Se nums può contenere duplicati, nessun algoritmo può garantire O(log n). Riesci a dimostrarlo? Crea una lista ruotata di 1 con un singolo 0 nascosto al suo interno, in cui qualsiasi ricerca di 0 debba leggere ogni elemento.
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Scegli un qualsiasi indice centrale e osserva le due metà ai suoi lati. La rotazione ha creato un punto in cui i valori diminuiscono, dal più grande al più piccolo. Entrambe le metà possono contenere quel calo?
Almeno una metà è sempre ordinata e confrontare
nums[lo]connums[mid]ti dice quale. Per una metà ordinata, puoi verificare in un solo passaggio setargetsi trova tra il suo primo e il suo ultimo valore.Mantieni
loehiintorno alla parte che potrebbe ancora conteneretarget. A ogni passaggio, se l’intervallo di valori della metà ordinata contienetarget, mantieni quella metà; altrimenti mantieni l’altra. Fermati quando trovitargeto quando l’intervallo è vuoto.
Soluzione
Una lista ordinata ruotata è formata da due sequenze ordinate messe una dopo l’altra: [15, 19, 23] e poi [2, 5, 8, 11]. La ricerca binaria semplice non funziona, perché confrontare target con il valore centrale non ti dice più da quale lato si trova target. La soluzione si basa su un fatto: ovunque tu divida la lista, almeno una delle due metà è completamente ordinata e, per una metà ordinata, puoi capire con un solo confronto se target può trovarsi al suo interno.
Esamina ogni elemento
Intuizione
Controlla ogni indice in ordine e restituisci il primo il cui valore è uguale a target. Se il ciclo termina senza trovare una corrispondenza, restituisci -1. I valori sono distinti, quindi la prima corrispondenza è l’unica e la scansione è corretta per qualsiasi lista, ruotata o meno.
Ignora tutto ciò che il problema ti dice. La lista è composta da due sequenze ordinate, eppure la scansione legge fino a tutti i 5000 elementi, mentre una ricerca binaria richiede circa 13 confronti. Il divario aumenta con l’input: un milione di elementi richiede un milione di confronti, contro circa 20. Il compito richiede O(log n), quindi questo è il punto di partenza da migliorare, non la risposta.
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 -1Trova il punto di rotazione, poi esegui una ricerca binaria
Intuizione
La lista ruotata è composta da due sequenze ordinate, e la seconda inizia dal valore più piccolo. Chiama il suo indice k. Una volta noto k, il problema si riduce a una semplice ricerca binaria: nums[k..n-1] è ordinata e contiene i valori da nums[k] a nums[n-1], mentre nums[0..k-1] è ordinata e contiene tutti i valori più grandi. Un confronto tra target e nums[k] e nums[n-1] determina quale sequenza cercare.
Per trovare k, esegui una ricerca binaria sul punto di discesa. Confronta il valore centrale con l’ultimo valore dell’intervallo, nums[hi]. Se nums[mid] > nums[hi], i valori diminuiscono in un punto dopo mid, quindi il valore più piccolo è alla sua destra: imposta lo = mid + 1. Altrimenti nums[mid..hi] cresce senza interruzioni, quindi il valore più piccolo è in mid o prima: imposta hi = mid, mantenendo mid nell’intervallo. Quando lo raggiunge hi, quell’indice è k.
Segui il primo esempio, [15, 19, 23, 2, 5, 8, 11] con target = 5. Il valore centrale 2 non è maggiore di 11, quindi hi diventa 3; poi 19 è maggiore di 2, quindi lo diventa 2; poi 23 è maggiore di 2, quindi lo diventa 3, e k = 3. Poiché 5 è compreso tra nums[3] = 2 e nums[6] = 11, cerca negli indici da 3 a 6: la ricerca binaria trova 5 all’indice 4. Due ricerche binarie richiedono circa 2 log2 n passaggi.
Algoritmo
- Imposta
lo = 0ehi = n-1. Mentrelo < hi, calcolamid; senums[mid] > nums[hi], impostalo = mid + 1, altrimenti impostahi = mid. - Chiama l’indice finale
k: contiene il valore più piccolo. - Se
nums[k] ≤ target ≤ nums[n-1], cerca negli indici dakan-1; altrimenti cerca negli indici da 0 ak-1. - Esegui una normale ricerca binaria in quell’intervallo e restituisci l’indice di
target, oppure-1se l’intervallo si svuota.
def search(nums, target):
n = len(nums)
# 1. Find k, the index of the smallest value, where the second run starts.
lo, hi = 0, n - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > nums[hi]:
lo = mid + 1 # the drop is right of mid
else:
hi = mid # mid is in the low run: the minimum is at mid or left of it
k = lo
# 2. nums[k..n-1] and nums[0..k-1] are sorted: search the one whose range holds target.
if nums[k] <= target <= nums[n - 1]:
lo, hi = k, n - 1
else:
lo, hi = 0, k - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1Una ricerca binaria sulla metà ordinata
Intuizione
Non devi sapere dove si trova il punto di rotazione. Mantieni la consueta garanzia della ricerca binaria: se target è nella lista, il suo indice si trova tra lo e hi. Guarda l’indice centrale mid. I valori scendono una sola volta nell’intera lista, quindi quel calo si trova al massimo in una delle due metà intorno a mid, mentre l’altra metà è ordinata.
Individua la metà ordinata con un confronto. Se nums[lo] ≤ nums[mid], la metà sinistra nums[lo..mid] non presenta cali ed è ordinata. Poiché sai già che nums[mid] non è target, target può trovarsi in quella metà solo se nums[lo] ≤ target < nums[mid]. In tal caso, imposta hi = mid - 1; altrimenti, target può trovarsi solo nell’altra metà, quindi imposta lo = mid + 1. Quando nums[lo] > nums[mid], il calo è a sinistra, la metà destra nums[mid..hi] è ordinata e decide il test speculare nums[mid] < target ≤ nums[hi]. Non ragioni mai direttamente sulla metà non ordinata: target si trova lì esattamente quando non può trovarsi nella metà ordinata.
Segui il primo esempio, [15, 19, 23, 2, 5, 8, 11] con target = 5. L’intervallo da 0 a 6 ha indice centrale 3, valore 2. Poiché 15 è maggiore di 2, la metà destra [2, 5, 8, 11] è ordinata e contiene 5, quindi lo diventa 4. L’intervallo da 4 a 6 ha indice centrale 5, valore 8. Ora nums[4] = 5 ≤ 8, la metà sinistra [5, 8] è ordinata e contiene 5, quindi hi diventa 4. L’indice 4 contiene 5: restituisci 4.
A ogni passaggio l’intervallo si dimezza, come nella normale ricerca binaria, quindi il ciclo viene eseguito al massimo circa log2(n) + 1 volte: 13 passaggi per 5000 elementi, con due indici di memoria aggiuntiva.
Algoritmo
- Imposta
lo = 0ehi = n-1. - Finché
lo ≤ hi, calcolamid. Senums[mid]è uguale atarget, restituiscimid. - Se
nums[lo] ≤ nums[mid], la metà sinistra è ordinata: senums[lo] ≤ target < nums[mid], impostahi = mid - 1, altrimenti impostalo = mid + 1. - Altrimenti, la metà destra è ordinata: se
nums[mid] < target ≤ nums[hi], 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[lo] <= nums[mid]:
# nums[lo..mid] is sorted: target is in it only if it fits its range
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
# nums[mid..hi] is sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
Trappole e casi limite
La ricerca in un solo passaggio è breve e quasi tutti i bug si trovano in un operatore di confronto.
- Scrivere
nums[lo] < nums[mid]invece di≤. Quando restano due elementi,midè uguale aloe la metà sinistra contiene un solo elemento, quindi è ordinata. Con il test stretto,[9, 4]etarget = 4fanno sì che[9, 4]venga considerata la metà destra ordinata; 4 viene cercato al di fuori dell'intervallo da 9 a 4 e viene restituito-1. - Confrontare prima
targetconnums[mid], come nella normale ricerca binaria. In[15, 19, 23, 2, 5, 8, 11]contarget = 19, il valore centrale 2 è minore di 19, quindi la ricerca si sposta a destra e non arriva mai all'indice 1. - Controllare un solo estremo della metà ordinata. In
[40, 50, 60, 70, 80, 10, 20]contarget = 80, il valore centrale è 70 e la metà sinistra[40, 50, 60, 70]è ordinata. Il controllotarget ≥ nums[lo]da solo sposta la ricerca a sinistra, perché 80 è maggiore di 40, ma 80 è anche maggiore di 70, quindi si trova nella metà destra. Controlla entrambi gli estremi. - Dimenticare il caso non ruotato nell'approccio in due passaggi. Quando
k = 0, la seconda esecuzione è vuota e il suo intervallo va da0a-1. Va bene con gli indici con segno, ma con quelli senza segno (usizedi Rust)k - 1va in underflow, ed è per questo che il codice Rust usa intervalli semiaperti. - Restituire direttamente la posizione in Lua e R. Le loro liste iniziano da 1, quindi sottrai 1 prima di restituire il risultato.
Domande frequenti4
Qual è la complessità temporale della ricerca in un array ordinato ruotato?
Tempo O(log n) e spazio aggiuntivo O(1). A ogni passaggio viene mantenuta una metà dell’intervallo corrente, proprio come nella ricerca binaria semplice, quindi un elenco di 5000 elementi richiede al massimo 13 passaggi. Anche la versione in due passaggi che individua prima il punto di rotazione è O(log n), con circa il doppio dei passaggi.
Come fai a sapere quale metà di un array ruotato è ordinata?
Confronta nums[lo] con nums[mid]. I valori diminuiscono una sola volta nell’intera lista. Se nums[lo] ≤ nums[mid], quel calo non si trova tra lo e mid, quindi la metà sinistra è ordinata. Altrimenti il calo si trova nella metà sinistra, il che significa che la metà destra, da mid a hi, non ne contiene e quindi è ordinata.
¿L’algoritmo funziona quando l’array contiene duplicati?
Non così com'è scritto. In [1, 0, 1, 1, 1], nums[lo], nums[mid] e nums[hi] sono tutti 1, quindi non è possibile dimostrare che nessuna delle due metà sia ordinata. La soluzione abituale è spostare lo avanti di uno quando nums[lo], nums[mid] e nums[hi] sono uguali: questo mantiene corretta la risposta, ma porta il caso peggiore a O(n).
Dovresti trovare prima il punto di rotazione o cercarlo in un unico passaggio?
Entrambi hanno complessità O(log n). Trovare prima l’indice del minimo suddivide il problema in due semplici ricerche binarie, così ogni parte riutilizza codice di cui ti fidi già. La ricerca in un solo passaggio svolge lo stesso compito in un unico ciclo con meno passaggi, ed è la versione che la maggior parte degli intervistatori si aspetta.
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
Caso 3
Input
nums = [15, 19, 23, 2, 5, 8, 11] target = 5
Atteso
4