Search in Rotated Sorted Array
Eine Liste verschiedener Ganzzahlen wurde aufsteigend sortiert und anschließend rotiert: Eine beliebige Anzahl von Elementen, möglicherweise null, wurde vorne entnommen und in derselben Reihenfolge ans Ende verschoben. Zum Beispiel wird [2, 5, 8, 11, 15, 19, 23], um 4 rotiert, zu [15, 19, 23, 2, 5, 8, 11]. Du erhältst die rotierte Liste nums und eine Ganzzahl target. Gib den Index von target in nums zurück, wobei ab 0 gezählt wird, oder -1, falls das Element nicht enthalten ist, und zwar in O(log n) Zeit.
Funktion
- numsinteger-array
- die rotierte sortierte Liste unterschiedlicher Ganzzahlen
- targetinteger
- der zu suchende Wert
- Gibt zurückinteger
- der Index von target in nums oder -1, falls es fehlt
Einschränkungen
1 ≤ nums.length ≤ 5000-104 ≤ nums[i], target ≤ 104- Alle Werte in
numssind verschieden. numsist eine aufsteigend sortierte Liste, die umkStellen rotiert wurde, wobei0 ≤ k < nums.lengthgilt;k = 0lässt sie unrotiert.
Beispiele
- Eingabe
- nums = [15, 19, 23, 2, 5, 8, 11]target = 5
- Ausgabe
- 4
- Erklärung
- Die erste Mitte, Index 3, enthält 2, also ist die rechte Hälfte
[2, 5, 8, 11]sortiert und enthält 5. Die nächste Mitte, Index 5, enthält 8; der sortierte linke Teil[5, 8]enthält 5, was zu Index 4 führt.
- Eingabe
- nums = [40, 50, 60, 70, 10, 20, 30]target = 65
- Ausgabe
- -1
- Erklärung
- 65 läge zwischen 60 und 70, und kein Element enthält es. Das erste mittlere Element, 70, ordnet 65 dem sortierten linken Teil
[40, 50, 60, 70]zu, und der Bereich verkleinert sich dort, bis er leer ist.
- Eingabe
- nums = [8, 13, 21, 1, 3, 5]target = 13
- Ausgabe
- 1
- Erklärung
- Das erste mittlere Element, Index 2, enthält 21. Der linke Teil
[8, 13, 21]ist sortiert und 13 liegt zwischen 8 und 21, also wird der rechte Teil verworfen. Die Suche findet 13 dann bei Index 1.
Weiterführende Frage
Wenn nums Duplikate enthalten kann, kann kein Algorithmus O(log n) garantieren. Kannst du das anhand einer rotierten Liste aus 1ern beweisen, in der sich eine einzelne 0 versteckt?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Wähle einen beliebigen mittleren Index und betrachte die beiden Hälften auf beiden Seiten davon. Durch die Rotation entstand eine Stelle, an der die Werte vom größten zum kleinsten abfallen. Können beide Hälften diesen Abfall enthalten?
Mindestens eine Hälfte ist immer sortiert, und der Vergleich von
nums[lo]mitnums[mid]verrät dir, welche es ist. Für eine sortierte Hälfte kannst du in einem Schritt prüfen, obtargetzwischen ihrem ersten und letzten Wert liegt.Behalte
loundhiso bei, dass sie den Teil begrenzen, dertargetnoch enthalten könnte. Wenn bei einem Schritt der Wertebereich der sortierten Hälftetargetenthält, behalte diese Hälfte bei; andernfalls behalte die andere Hälfte bei. Beende die Suche, wenn dutargetfindest oder der Bereich leer ist.
Lösung
Eine gedrehte sortierte Liste besteht aus zwei sortierten Abschnitten: [15, 19, 23] und dann [2, 5, 8, 11]. Ein Vergleich von target mit dem mittleren Wert verrät dir nicht mehr, auf welcher Seite sich der Wert befindet. Doch egal, wo du die Liste teilst: Mindestens eine Hälfte ist sortiert, und ein Vergleich zeigt dir, ob sich target in dieser Hälfte befinden kann.
Durchsuche jedes Element
Idee
Überprüfe jeden Index und gib den ersten zurück, dessen Wert target entspricht, oder nach der Schleife -1. Dabei wird jedes Element gelesen, daher funktioniert es für jede Liste. Die beiden sortierten Teilbereiche werden ignoriert: Bei 5000 Elementen sind bis zu 5000 Vergleiche nötig, während eine binäre Suche 13 benötigt.
Algorithmus
- Vergleiche für jeden Index
ivon 0 bisn-1nums[i]mittarget. - Wenn sie gleich sind, gib
izurück. - Gib nach der Schleife
-1zurück.
def search(nums, target):
for i, value in enumerate(nums):
if value == target:
return i
return -1Finde den Rotationspunkt und führe dann eine binäre Suche durch
Idee
Der zweite Lauf beginnt beim kleinsten Wert; nenne seinen Index k. Sowohl nums[k..n-1] als auch nums[0..k-1] sind sortiert, und jeder Wert im ersten Lauf ist größer als jeder Wert im zweiten. Sobald du k kennst, bestimmt der Vergleich von target mit nums[k] und nums[n-1], in welchem Lauf gesucht wird, und eine gewöhnliche binäre Suche erledigt den Rest.
Um k zu finden, vergleiche den mittleren Wert mit nums[hi]. Wenn nums[mid] > nums[hi] gilt, fallen die Werte irgendwo nach mid ab, also liegt das Minimum rechts davon. Andernfalls steigt nums[mid..hi] ohne Abfall an, also liegt das Minimum bei mid oder davor. Im ersten Beispiel sind die mittleren Werte 2, 19 und 23, woraus k = 3 folgt, und 5 liegt zwischen nums[3] = 2 und nums[6] = 11. Zwei binäre Suchen kosten etwa 2 log2 n Schritte.
Algorithmus
- Setze
lo = 0undhi = n-1. Solangelo < higilt, berechnemid; wennnums[mid] > nums[hi]gilt, setzelo = mid + 1, andernfalls setzehi = mid. - Der endgültige Index
kenthält den kleinsten Wert. - Wenn
nums[k] ≤ target ≤ nums[n-1]gilt, führe eine binäre Suche in den Indizeskbisn-1durch; andernfalls suche von 0 bisk-1. - Gib den gefundenen Index zurück oder
-1, wenn der Bereich leer ist.
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 -1Eine binäre Suche auf der sortierten Hälfte
Idee
Halte am Versprechen der binären Suche fest: Wenn target in der Liste vorkommt, liegt sein Index zwischen lo und hi. Die Werte fallen in der gesamten Liste nur einmal ab, daher enthält höchstens eine der beiden Hälften um mid den Abfall, während die andere sortiert ist. Wenn nums[lo] ≤ nums[mid] gilt, ist die linke Hälfte sortiert; andernfalls ist es die rechte.
Für die sortierte Hälfte zeigt ein Bereichstest anhand ihrer beiden Enden, ob sich target darin befinden kann, zum Beispiel nums[lo] ≤ target < nums[mid] auf der linken Seite. Wenn ja, suche dort; wenn nicht, kann target nur in der anderen Hälfte liegen. Bei jedem Schritt halbiert sich der Bereich: Bei 5000 Elementen sind höchstens 13 Schritte nötig.
Algorithmus
- Setze
lo = 0undhi = n-1. - Berechne, solange
lo ≤ higilt,midund gib den Wert zurück, wennnums[mid]gleichtargetist. - Wenn
nums[lo] ≤ nums[mid]gilt, ist die linke Hälfte sortiert: Setzehi = mid - 1, wennnums[lo] ≤ target < nums[mid]gilt, andernfallslo = mid + 1. - Andernfalls ist die rechte Hälfte sortiert: Setze
lo = mid + 1, wennnums[mid] < target ≤ nums[hi]gilt, andernfallshi = mid - 1. - Wenn die Schleife endet, gib
-1zurück.
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
Stolperfallen und Grenzfälle
nums[lo] < nums[mid]statt≤schreiben. Wenn noch zwei Elemente übrig sind, istmidgleichlo, und der strenge Test behandelt[9, 4]als sortierte rechte Hälfte:target = 4gibt-1zurück.targetzuerst mitnums[mid]vergleichen. Im ersten Beispiel mittarget = 19ist die mittlere 2 kleiner, daher bewegt sich die Suche nach rechts und verfehlt Index 1.- Nur ein Ende der sortierten Hälfte testen. Bei
[40, 50, 60, 70, 80, 10, 20]mittarget = 80schickttarget ≥ nums[lo]allein die Suche in[40, 50, 60, 70]. - In Rust läuft
k - 1bei einemusizeüber, wennk = 0, also bei der nicht rotierten Liste. Verwende halboffene Bereiche. - In Lua und R die 1-basierte Position zurückgeben. Ziehe 1 ab.
Häufige Fragen3
Wie hoch ist die Zeitkomplexität der Suche in einem gedrehten, sortierten Array?
O(log n) Zeit und O(1) zusätzlicher Speicherplatz. Bei jedem Schritt bleibt eine Hälfte des Bereichs erhalten, daher sind für 5000 Elemente höchstens 13 Schritte erforderlich. Zuerst den Rotationspunkt zu finden, ist ebenfalls O(log n) und benötigt etwa doppelt so viele Schritte.
Funktioniert der Algorithmus, wenn das Array Duplikate enthält?
Nicht in der vorliegenden Form. Wenn nums[lo], nums[mid] und nums[hi] gleich sind, lässt sich nicht beweisen, dass eine der beiden Hälften sortiert ist. Die übliche Lösung erhöht in diesem Fall lo um eins. Dadurch bleibt das Ergebnis korrekt, aber die Worst-Case-Laufzeit beträgt O(n).
Solltest du zuerst den Rotationspunkt finden oder in einem Durchgang suchen?
Beide laufen in O(log n). Zuerst das Minimum zu finden, teilt das Problem in zwei einfache binäre Suchen auf. Die Suche in einem Durchlauf erledigt die Aufgabe in einer einzigen Schleife mit weniger Schritten und ist die Variante, die die meisten Interviewer erwarten.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def search(nums, target):
# Schreibe hier den CodeTest #1
Test #2
Test #3
Argumente
nums = [15, 19, 23, 2, 5, 8, 11] target = 5
Erwartete Ausgabe
4