Binäre Suche in rotierten und unsortierten Arrays

Ein rotiertes sortiertes Array ist ein sortiertes Array, das an einem bestimmten Drehpunkt geteilt wurde und dessen beide Teile vertauscht wurden. Beispielsweise ist [4, 5, 6, 7, 0, 1, 2] das bei Index 4 rotierte sortierte Array [0,1,2,4,5,6,7]. Die standardmäßige binäre Suche schlägt hier fehl, weil das Array nicht mehr global sortiert ist.

Die zentrale Erkenntnis ist, dass nach jeder Rotation mindestens eine Hälfte des Arrays immer sortiert ist. Ihre binäre Suche muss erkennen, welche Hälfte sortiert ist, bevor sie entscheidet, wie die Grenzen verschoben werden.

Nachdem Sie mid berechnet haben, vergleichen Sie arr[lo] mit arr[mid]. Wenn arr[lo] <= arr[mid] gilt, ist die linke Hälfte sortiert; andernfalls ist die rechte Hälfte sortiert. Sobald Sie wissen, welche Hälfte sortiert ist, können Sie prüfen, ob das Ziel in diesem sortierten Bereich liegt, und die Suche entsprechend eingrenzen.

Mit diesem Entscheidungsbaum können Sie in jedem Schritt genau die Hälfte des Arrays verwerfen. Dadurch bleibt die Komplexität auch bei einem rotierten Array O(log n).

Verfolgen wir search_rotated([4,5,6,7,0,1,2], 0) Schritt für Schritt. Zu Beginn gilt lo=0, hi=6, mid=3, arr[mid]=7. Liegt das Ziel 0 in der sortierten linken Hälfte [4..7]? Nein, also setzen wir lo=4. Nun gilt lo=4, hi=6, mid=5, arr[mid]=1. Die linke Hälfte [0,1] ist sortiert (arr[lo]=0 <= arr[mid]=1). Liegt 0 in [0..1)? Ja, also setzen wir hi=4. Nun gilt lo=4, hi=4, mid=4, arr[4]=0 — das Element wurde an Index 4 gefunden.

Wenn das rotierte Array Duplikate enthalten kann (z. B. [1,3,1,1,1]), ist die Bedingung nums[lo] == nums[mid] nicht eindeutig — Sie können nicht feststellen, welche Hälfte sortiert ist. Die sichere Lösung besteht darin, lo um eins zu erhöhen (oder hi um eins zu verringern) und es erneut zu versuchen. Dadurch verschlechtert sich die Laufzeit im Worst Case auf O(n). Diesen Umstand sollten Sie im Vorstellungsgespräch erwähnen.

Bei einer verwandten Aufgabe soll das Minimum in einem rotierten sortierten Array gefunden werden, ohne nach einem bestimmten Zielwert zu suchen. Das Minimum liegt immer in der unsortierten Hälfte. In jedem Schritt gilt: Wenn arr[mid] > arr[hi], liegt das Minimum in der rechten Hälfte (lo = mid + 1); andernfalls liegt es in der linken Hälfte einschließlich mid (hi = mid). Sobald lo == hi gilt, haben Sie das Minimum gefunden.

Die Bedingung arr[lo] <= arr[mid] funktioniert, weil in einem sortierten (oder nicht rotierten) Abschnitt das erste Element immer das kleinste ist. Wenn arr[lo] <= arr[mid] gilt, wurde innerhalb von [lo..mid] keine Rotation durchgeführt, sodass diese Hälfte sortiert ist. Die Gleichheit berücksichtigt den Fall lo == mid (ein Abschnitt mit einem einzigen Element ist trivialerweise sortiert).

Wenn dagegen arr[lo] > arr[mid] gilt, muss der Rotations-Pivot zwischen lo und mid liegen. Daher ist die rechte Hälfte [mid..hi] der zusammenhängende sortierte Abschnitt.

Die Suche in einem rotierten sortierten Array mit binärer Suche benötigt weiterhin O(log n) Zeit und O(1) Speicherplatz, da wir den Suchbereich in jeder Iteration halbieren. Der einzige Unterschied zur klassischen binären Suche ist eine zusätzliche Prüfung mit konstanter Laufzeit, um festzustellen, welche Hälfte sortiert ist.

Bei Duplikaten verschlechtert sich die Laufzeit im Worst Case auf O(n), weil wir lo in jedem Schritt möglicherweise nur um eins erhöhen können. Erwähnen Sie diesen Kompromiss ausdrücklich — dadurch zeigen Sie, dass Sie auch über Randfälle jenseits des normalen Ablaufs nachdenken.

LeetCode 33 „Search in Rotated Sorted Array“ ist die kanonische Form dieser Aufgabe. Die Einschränkungen garantieren keine Duplikate und genau eine Rotation. Die Lösung ist die zuvor geschriebene Funktion search_rotated. Wichtige Punkte im Vorstellungsgespräch: Nennen Sie immer die Annahme, dass keine Duplikate vorhanden sind, überprüfen Sie Ihre Ungleichungen anhand eines konkreten Beispiels an der Grenze und stellen Sie sicher, dass der zurückgegebene Index sowohl im Fall eines gefundenen als auch im Fall eines nicht gefundenen Elements korrekt ist.

LeetCode 153 „Find Minimum in Rotated Sorted Array“ verlangt, das Minimum ohne Duplikate zu finden. Vergleichen Sie dazu arr[mid] mit arr[hi] (nicht mit arr[lo]), um zu bestimmen, auf welcher Seite das Minimum liegt. Wenn arr[mid] > arr[hi] gilt, liegt das Minimum rechts; andernfalls liegt es bei mid oder links davon. So nähern Sie sich dem Minimum in O(log n).

Sobald Sie das Minimum finden können, kennen Sie auch die Rotationsanzahl: Der Index des Minimums entspricht genau der Anzahl der Positionen, um die das Array nach rechts rotiert wurde. Im Beispiel [4,5,6,7,0,1,2] liegt das Minimum an Index 4, also wurde das Array um 4 Positionen rotiert.

Wenn Sie den Pivot kennen, können Sie eine Standard-Binärsuche anwenden, indem Sie die Indizes modulo n behandeln: real_idx = (mid + pivot) % n. Diese alternative Formulierung kann die Überlegungen bei der Arbeit mit zirkulär indizierten Strukturen vereinfachen.

Wenn Sie in einem Vorstellungsgespräch auf eine Aufgabe mit einem rotierten Array stoßen, folgen Sie diesem Entscheidungsbaum. Bestimmen Sie zunächst, ob Sie ein Ziel finden oder das Minimum finden müssen. Verwenden Sie zum Finden eines Zielwerts den Ansatz zur Erkennung der sortierten Hälfte. Um das Minimum zu finden, vergleichen Sie mid mit hi. Wenn Duplikate möglich sind, erwähnen Sie den Worst Case O(n) und ergänzen Sie die Fallback-Logik zum Verkleinern des Randbereichs.

Üben Sie, indem Sie Ihren Code anhand der drei klassischen Beispiele nachvollziehen: keine Rotation, einmal rotiert und so rotiert, dass das Minimum an der letzten Position steht.

Testen Sie Ihr Verständnis der Konzepte aus dieser Lektion zu Data Structures & Algorithms — Coding Interview Prep.

In dieser Lektion haben Sie gelernt: Ein rotiertes sortiertes Array hat immer mindestens eine sortierte Hälfte, Vergleichen Sie arr[lo] mit arr[mid], um vor der Entscheidung über den weiteren Suchbereich die sortierte Hälfte zu bestimmen, und zum Finden des Minimums wird arr[mid] mit arr[hi] verglichen, um den Rotations-Pivot zu lokalisieren. Als Nächstes sehen wir uns Varianten der binären Suche mit Lower Bound und Upper Bound an.