Search in Rotated Sorted Array
Eine Liste unterschiedlicher Ganzzahlen wurde aufsteigend sortiert und anschließend rotiert: Eine beliebige Anzahl von Elementen, möglicherweise null, wurde vom Anfang genommen 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 sie nicht enthalten ist, und zwar in O(log n)-Zeit.
Funktion
- numsinteger-array
- die gedrehte sortierte Liste unterschiedlicher Ganzzahlen
- targetinteger
- der gesuchte Wert
- Gibt zurückinteger
- der Index von target in nums oder -1, falls es nicht vorhanden ist
Einschränkungen
1 ≤ nums.length ≤ 5000-104 ≤ nums[i], target ≤ 104- Alle Werte in
numssind verschieden. numsist eine aufsteigende Liste, die um ein bestimmteskrotiert 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
- 5 befindet sich an Index 4. Das erste mittlere Element, Index 3, enthält 2, daher ist die rechte Hälfte
[2, 5, 8, 11]sortiert, und 5 liegt zwischen 2 und 11. Das nächste mittlere Element, 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 würde zwischen 60 und 70 liegen, und kein Element enthält diesen Wert. Das erste mittlere Element, 70 an Index 3, ordnet 65 dem sortierten linken Teil
[40, 50, 60, 70]zu. Der Bereich verkleinert sich innerhalb dieses Abschnitts, bis er leer ist, daher gibt die Funktion-1zurück.
- 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 gesamte rechte Teil verworfen. Die Suche findet 13 dann bei Index 1.
+23 versteckte Tests beim Einreichen
Weiterführende Frage
Wenn nums Duplikate enthalten kann, kann kein Algorithmus O(log n) garantieren. Kannst du das beweisen? Erstelle eine gedrehte Liste aus 1ern, in der eine einzelne 0 versteckt ist und bei der jede Suche nach 0 jedes Element lesen muss.
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Wähle einen beliebigen Index in der Mitte 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]zeigt dir, welche das ist. Bei einer sortierten Hälfte kannst du in einem Schritt prüfen, obtargetzwischen ihrem ersten und letzten Wert liegt.Behalte
loundhium den Teil, dertargetnoch enthalten könnte. Prüfe bei jedem Schritt, ob der Wertebereich der sortierten Hälftetargetenthält. Falls ja, behalte diese Hälfte; andernfalls behalte die andere. Beende die Suche, wenn dutargetfindest oder der Bereich leer ist.
Lösung
Eine rotiert sortierte Liste besteht aus zwei sortierten Abschnitten, die direkt aufeinanderfolgen: [15, 19, 23] und dann [2, 5, 8, 11]. Die gewöhnliche binäre Suche funktioniert damit nicht, denn der Vergleich von target mit dem mittleren Wert verrät nicht mehr, auf welcher Seite sich target befindet. Die Lösung beruht auf einer Tatsache: Egal, wo du die Liste teilst, mindestens eine der beiden Hälften ist vollständig sortiert, und bei einer sortierten Hälfte kannst du mit einem Vergleich feststellen, ob target darin liegen kann.
Scanne jedes Element
Idee
Prüfe jeden Index der Reihe nach und gib den ersten zurück, dessen Wert gleich target ist. Wenn die Schleife ohne Treffer endet, gib -1 zurück. Die Werte sind verschieden, daher ist der erste Treffer der einzige, und die Suche ist für jede Liste korrekt, ob rotiert oder nicht.
Das ignoriert alles, was die Aufgabe vorgibt. Die Liste besteht aus zwei sortierten Abschnitten, dennoch liest die Suche bis zu alle 5000 Elemente, während eine binäre Suche etwa 13 Vergleiche benötigt. Mit zunehmender Eingabe wächst der Abstand: Bei einer Million Elementen sind eine Million Vergleiche nötig, gegenüber etwa 20. Die Aufgabe verlangt O(log n); dies ist also die Ausgangsbasis, die verbessert werden soll, nicht die Lösung.
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
Die gedrehte Liste besteht aus zwei sortierten Abschnitten, und der zweite beginnt mit dem kleinsten Wert. Nenne seinen Index k. Sobald du k kennst, wird das Problem zu einer einfachen binären Suche: nums[k..n-1] ist sortiert und enthält die Werte von nums[k] bis nums[n-1], und nums[0..k-1] ist sortiert und enthält alle größeren Werte. Ein Vergleich von target mit nums[k] und nums[n-1] entscheidet, in welchem Abschnitt gesucht wird.
Um k zu finden, führe eine binäre Suche nach dem Abfall durch. Vergleiche den mittleren Wert mit dem letzten Wert des Bereichs, nums[hi]. Wenn nums[mid] > nums[hi], fallen die Werte irgendwo nach mid, also liegt der kleinste Wert rechts davon: Setze lo = mid + 1. Andernfalls steigt nums[mid..hi] ohne Abfall an, also liegt der kleinste Wert bei mid oder davor: Setze hi = mid, damit mid im Bereich bleibt. Wenn lo und hi übereinstimmen, ist dieser Index k.
Verfolge das erste Beispiel: [15, 19, 23, 2, 5, 8, 11] mit target = 5. Die mittlere 2 ist nicht größer als 11, also wird hi zu 3; dann ist 19 größer als 2, also wird lo zu 2; danach ist 23 größer als 2, also wird lo zu 3, und k = 3. Da 5 zwischen nums[3] = 2 und nums[6] = 11 liegt, suche an den Indizes 3 bis 6. Dort findet die binäre Suche 5 am Index 4. Zwei binäre Suchen kosten ungefähr 2 log2 n Schritte.
Algorithmus
- Setze
lo = 0undhi = n-1. Solangelo < higilt, berechnemid; wennnums[mid] > nums[hi]gilt, setzelo = mid + 1, andernfalls setzehi = mid. - Nenne den endgültigen Index
k: Dort steht der kleinste Wert. - Wenn
nums[k] ≤ target ≤ nums[n-1]gilt, durchsuche die Indizeskbisn-1; andernfalls durchsuche die Indizes 0 bisk-1. - Führe eine einfache binäre Suche in diesem Bereich aus und gib den Index von
targetzurück oder-1, wenn der Bereich leer wird.
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 in der sortierten Hälfte
Idee
Du musst nicht wissen, wo der Drehpunkt liegt. Behalte die übliche Zusicherung der binären Suche bei: Wenn target in der Liste ist, liegt sein Index zwischen lo und hi. Betrachte den mittleren Index mid. Die Werte fallen in der gesamten Liste nur einmal ab, daher liegt dieser Abfall in höchstens einer der beiden Hälften um mid, und die andere Hälfte ist sortiert.
Finde mit einem Vergleich die sortierte Hälfte. Wenn nums[lo] ≤ nums[mid], enthält die linke Hälfte nums[lo..mid] keinen Abfall und ist sortiert. Da du bereits weißt, dass nums[mid] nicht target ist, kann target nur dann in dieser Hälfte liegen, wenn nums[lo] ≤ target < nums[mid]. Wenn das zutrifft, setze hi = mid - 1; andernfalls kann target nur in der anderen Hälfte liegen, also setze lo = mid + 1. Wenn nums[lo] > nums[mid], liegt der Abfall links, die rechte Hälfte nums[mid..hi] ist sortiert, und der entsprechende Test nums[mid] < target ≤ nums[hi] entscheidet. Du denkst nie direkt über die unsortierte Hälfte nach: target kommt genau dann in sie, wenn die sortierte Hälfte nicht infrage kommt.
Verfolge das erste Beispiel: [15, 19, 23, 2, 5, 8, 11] mit target = 5. Der Bereich von 0 bis 6 hat den mittleren Index 3 mit dem Wert 2. Da 15 größer als 2 ist, ist die rechte Hälfte [2, 5, 8, 11] sortiert und enthält 5, also wird lo auf 4 gesetzt. Der Bereich von 4 bis 6 hat den mittleren Index 5 mit dem Wert 8. Nun gilt nums[4] = 5 ≤ 8; die linke Hälfte [5, 8] ist sortiert und enthält 5, also wird hi auf 4 gesetzt. An Index 4 steht 5: Gib 4 zurück.
Bei jedem Schritt wird der Bereich halbiert, wie bei einer einfachen binären Suche, daher wird die Schleife höchstens ungefähr log2(n) + 1 Mal ausgeführt: 13 Schritte bei 5000 Elementen, mit zwei zusätzlichen Indizes an Speicherbedarf.
Algorithmus
- Setze
lo = 0undhi = n-1. - Solange
lo ≤ higilt, berechnemid. Wennnums[mid]gleichtargetist, gibmidzurück. - Wenn
nums[lo] ≤ nums[mid]gilt, ist die linke Hälfte sortiert: Wennnums[lo] ≤ target < nums[mid]gilt, setzehi = mid - 1, andernfalls setzelo = mid + 1. - Andernfalls ist die rechte Hälfte sortiert: Wenn
nums[mid] < target ≤ nums[hi]gilt, setzelo = mid + 1, andernfalls setzehi = 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
Die Suche in einem Durchlauf ist kurz, und fast jeder Fehler steckt in einem Vergleichsoperator.
- Schreibe
nums[lo] < nums[mid]statt≤. Wenn noch zwei Elemente übrig sind, istmidgleichlo, und die linke Hälfte besteht aus einem Element, das sortiert ist. Mit dem strikten Test behandeln[9, 4]undtarget = 4[9, 4]als sortierte rechte Hälfte, finden 4 außerhalb des Bereichs von 9 bis 4 und geben-1zurück. targetzuerst mitnums[mid]vergleichen, wie bei einer gewöhnlichen binären Suche. Bei[15, 19, 23, 2, 5, 8, 11]mittarget = 19ist der mittlere Wert 2 kleiner als 19, also bewegt sich die Suche nach rechts und sieht Index 1 nie.- Nur ein Ende der sortierten Hälfte prüfen. Bei
[40, 50, 60, 70, 80, 10, 20]mittarget = 80ist der mittlere Wert 70, und die linke Hälfte[40, 50, 60, 70]ist sortiert. Die alleinige Prüfungtarget ≥ nums[lo]schickt die Suche nach links, weil 80 größer als 40 ist. Aber 80 ist auch größer als 70, liegt also in der rechten Hälfte. Prüfe beide Enden. - Den nicht rotierten Fall beim Ansatz in zwei Schritten vergessen. Wenn
k = 0, ist der zweite Durchlauf leer, und sein Bereich reicht von0bis-1. Mit vorzeichenbehafteten Indizes ist das in Ordnung, aber bei vorzeichenlosen Indizes (Rustsusize) läuftk - 1unter, weshalb der Rust-Code halboffene Bereiche verwendet. - In Lua und R die Position selbst zurückgeben. Ihre Listen beginnen bei 1, also musst du vor der Rückgabe 1 abziehen.
Häufige Fragen4
Wie hoch ist die Zeitkomplexität bei der Suche in einem rotierten sortierten Array?
O(log n) Zeit und O(1) zusätzlicher Speicherplatz. Bei jedem Schritt wird eine Hälfte des aktuellen Bereichs beibehalten, genau wie bei der einfachen binären Suche, sodass eine Liste mit 5000 Elementen höchstens 13 Schritte benötigt. Die zweistufige Variante, die zuerst den Rotationspunkt findet, ist ebenfalls O(log n) und benötigt ungefähr doppelt so viele Schritte.
Woran erkennst du, welche Hälfte eines gedrehten Arrays sortiert ist?
Vergleiche nums[lo] mit nums[mid]. Die Werte fallen in der gesamten Liste nur einmal ab. Wenn nums[lo] ≤ nums[mid], liegt dieser Abfall nicht zwischen lo und mid, also ist die linke Hälfte sortiert. Andernfalls liegt der Abfall in der linken Hälfte, was bedeutet, dass die rechte Hälfte von mid bis hi keinen Abfall enthält und sortiert ist.
Funktioniert der Algorithmus, wenn das Array Duplikate enthält?
Nicht in der vorliegenden Form. In [1, 0, 1, 1, 1] sind nums[lo], nums[mid] und nums[hi] alle 1, daher lässt sich nicht beweisen, dass eine der beiden Hälften sortiert ist. Üblicherweise wird lo um eins nach vorne verschoben, wenn nums[lo], nums[mid] und nums[hi] gleich sind. Dadurch bleibt das Ergebnis korrekt, aber im Worst Case beträgt die Laufzeit O(n).
Solltest du zuerst den Drehpunkt finden oder in einem Durchgang suchen?
Beide laufen in O(log n). Die Suche nach dem Index des Minimums zerlegt das Problem zunächst in zwei einfache binäre Suchläufe, sodass jeder Teil Code wiederverwendet, dem du bereits vertraust. Die Suche in einem Durchlauf erledigt dieselbe Aufgabe in einer einzigen Schleife mit weniger Schritten und ist die Version, die die meisten Interviewer erwarten.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
Python
def search(nums, target):
# Schreibe hier deinen CodeFall 1
Fall 2
Fall 3
Eingabe
nums = [15, 19, 23, 2, 5, 8, 11] target = 5
Erwartet
4