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, [2, 5, 8, 11, 15, 19, 23] ruotato di 4 diventa [15, 19, 23, 2, 5, 8, 11]. Ti vengono dati 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, o -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
- Il primo elemento centrale, indice 3, contiene 2, quindi la metà destra
[2, 5, 8, 11]è ordinata e contiene 5. Il successivo elemento centrale, 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 si troverebbe tra 60 e 70, e nessun elemento lo contiene. Il primo elemento centrale, 70, colloca 65 nella parte sinistra ordinata
[40, 50, 60, 70], e l’intervallo si restringe lì finché non è vuoto.
- 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 la parte destra viene scartata. La ricerca trova poi 13 all’indice 1.
Per approfondire
Se nums può contenere duplicati, nessun algoritmo può garantire O(log n). Riesci a dimostrarlo con una lista ruotata di 1 che nasconde un singolo 0?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Scegli un indice qualsiasi nel mezzo e osserva le due metà ai suoi lati. La rotazione ha creato un punto in cui i valori scendono, dal più grande al più piccolo. Entrambe le metà possono contenere quel punto di discesa?
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 è composta da due sequenze ordinate: [15, 19, 23] e poi [2, 5, 8, 11]. Confrontare target con il valore centrale non ti dice più da quale parte si trova. Ma, ovunque tu divida la lista, almeno una metà è ordinata e un confronto ti dice se target può trovarsi in quella metà.
Esamina ogni elemento
Intuizione
Controlla ogni indice e restituisci il primo il cui valore è uguale a target, oppure -1 dopo il ciclo. Legge ogni elemento, quindi è corretto per qualsiasi lista. Ignora i due tratti ordinati: 5000 elementi richiedono fino a 5000 confronti, mentre una ricerca binaria ne richiede 13.
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 seconda sequenza inizia dal valore più piccolo; chiama il suo indice k. Sia nums[k..n-1] che nums[0..k-1] sono ordinati e ogni valore della prima sequenza è maggiore di ogni valore della seconda. Una volta noto k, confrontare target con nums[k] e nums[n-1] permette di scegliere la sequenza, poi una normale ricerca binaria conclude il lavoro.
Per trovare k, confronta il valore centrale con nums[hi]. Se nums[mid] > nums[hi], i valori diminuiscono da qualche parte dopo mid, quindi il minimo si trova alla sua destra. Altrimenti nums[mid..hi] cresce senza diminuzioni, quindi il minimo si trova in corrispondenza di mid o prima. Nel primo esempio i valori centrali sono 2, 19 e 23, perciò si ottiene k = 3, e 5 si trova tra nums[3] = 2 e nums[6] = 11. Due ricerche binarie richiedono circa 2 log2 n passaggi.
Algoritmo
- Imposta
lo = 0ehi = n-1. Finchélo < hi, calcolamid; senums[mid] > nums[hi], impostalo = mid + 1, altrimenti impostahi = mid. - L’indice finale
kcontiene il valore più piccolo. - Se
nums[k] ≤ target ≤ nums[n-1], esegui una ricerca binaria sugli indici dakan-1; altrimenti cerca da 0 ak-1. - Restituisci l’indice trovato 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
Mantieni la promessa della ricerca binaria: se target è nell’elenco, il suo indice si trova tra lo e hi. I valori diminuiscono una sola volta nell’intero elenco, quindi al massimo una delle due metà ai lati di mid contiene la discesa, mentre l’altra è ordinata. Se nums[lo] ≤ nums[mid], la metà sinistra è ordinata; altrimenti lo è quella destra.
Per la metà ordinata, un controllo dell’intervallo ai suoi due estremi indica se target può trovarsi al suo interno, per esempio nums[lo] ≤ target < nums[mid] a sinistra. Se può, cerca lì; altrimenti, target può trovarsi solo nell’altra metà. A ogni passaggio l’intervallo si dimezza: al massimo 13 passaggi per 5000 elementi.
Algoritmo
- Imposta
lo = 0ehi = n-1. - Finché
lo ≤ hi, calcolamide restituiscilo senums[mid]è uguale atarget. - Se
nums[lo] ≤ nums[mid], la metà sinistra è ordinata: impostahi = mid - 1quandonums[lo] ≤ target < nums[mid], altrimentilo = mid + 1. - Altrimenti, la metà destra è ordinata: imposta
lo = mid + 1quandonums[mid] < target ≤ nums[hi], altrimentihi = 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
- Scrivere
nums[lo] < nums[mid]invece di≤. Quando restano due elementi,midè uguale aloe il test rigoroso considera[9, 4]una metà destra ordinata:target = 4restituisce-1. - Confrontare prima
targetconnums[mid]. Nel primo esempio contarget = 19, il valore centrale 2 è minore, quindi la ricerca si sposta a destra e non trova l'indice 1. - Controllare solo un estremo della metà ordinata. In
[40, 50, 60, 70, 80, 10, 20]contarget = 80,target ≥ nums[lo]da solo sposta la ricerca in[40, 50, 60, 70]. - In Rust,
k - 1su unusizeva in underflow quandok = 0, cioè nella lista non ruotata. Usa intervalli semiaperti. - In Lua e R, restituire la posizione a base 1. Sottrai 1.
Domande frequenti3
Qual è la complessità temporale della ricerca in un array ordinato ruotato?
Tempo O(log n) e spazio aggiuntivo O(1). A ogni passaggio si mantiene una metà dell'intervallo, quindi per 5000 elementi servono al massimo 13 passaggi. Trovare prima il punto di rotazione richiede anch'esso O(log n), con circa il doppio dei passaggi.
l'algoritmo funziona quando l'array contiene duplicati?
Non così com'è scritto. Quando nums[lo], nums[mid] e nums[hi] sono uguali, non è possibile dimostrare che una delle due metà sia ordinata. La soluzione abituale consiste nell'avanzare lo di uno in questo caso, mantenendo corretta la risposta ma portando il caso peggiore a O(n).
Dovresti trovare prima il punto di rotazione o cercarlo in un'unica passata?
Entrambi hanno complessità O(log n). Trovare prima il minimo suddivide il problema in due semplici ricerche binarie. La ricerca in un solo passaggio svolge il compito con un unico ciclo e 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.
def search(nums, target):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomenti
nums = [15, 19, 23, 2, 5, 8, 11] target = 5
Output atteso
4