Was ist ein rotiertes sortiertes Array?

Stellen Sie sich ein sortiertes Array vor, zum Beispiel:

[1, 2, 3, 4, 5, 6]

Wenn dieses Array nun an einem Drehpunkt gedreht wird, beispielsweise an Index 3, würde es wie folgt aussehen:

[4, 5, 6, 1, 2, 3]

Beachten Sie, dass das Array immer noch sortiert, aber in zwei Teile unterteilt ist. Unser Ziel ist es, in solchen Arrays effizient nach einem Zielwert zu suchen.

Die Suchstrategie

Um in einem gedrehten sortierten Array zu suchen, müssen wir Folgendes tun:

1. Finden Sie den Pivot: Der Pivot ist der Punkt, an dem das Array von größeren zu kleineren Werten übergeht.
2. Binäre Suche: Sobald wir den Pivot gefunden haben, können wir die binäre Suche in der entsprechenden Hälfte des Arrays verwenden.

Schritt-für-Schritt-Code-Erklärung

class Solution {
    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 1, 2, 3}; // Example of rotated sorted array
        int target = 5;

        // Searching for the target
        int result = search(arr, target);

        // Displaying the result
        System.out.println("Index of target: "   result);
    }

    // Main search function to find the target in a rotated sorted array
    public static int search(int[] nums, int target) {
        // Step 1: Find the pivot
        int pivot = searchPivot(nums);

        // Step 2: If no pivot, perform regular binary search
        if (pivot == -1) {
            return binarySearch(nums, target, 0, nums.length - 1);
        }

        // Step 3: If the target is at the pivot, return the pivot index
        if (nums[pivot] == target) {
            return pivot;
        }

        // Step 4: Decide which half of the array to search
        if (target >= nums[0]) {
            return binarySearch(nums, target, 0, pivot - 1); // Search left side
        } else {
            return binarySearch(nums, target, pivot   1, nums.length - 1); // Search right side
        }
    }

    // Binary search helper function
    static int binarySearch(int[] arr, int target, int start, int end) {
        while (start  arr[mid   1]) {
                return mid;
            }

            // Check if the pivot is before the mid
            if (mid > start && arr[mid] 





  
  
  Erläuterung des Kodex



suchen():

Diese Funktion ist für die Suche nach dem Ziel im gedrehten sortierten Array verantwortlich.
Zuerst finden wir den Pivot mit der Funktion searchPivot().
Abhängig von der Position des Pivots entscheiden wir dann, welche Hälfte des Arrays mithilfe der binären Suche durchsucht werden soll.


binarySearch():

Ein standardmäßiger binärer Suchalgorithmus, um das Ziel in einem sortierten Unterarray zu finden.
Wir definieren die Start- und Endindizes und grenzen den Suchraum schrittweise ein.


searchPivot():

Diese Funktion identifiziert den Drehpunkt (den Ort, an dem sich das Array dreht).
Der Pivot ist der Index, an dem die Sortierreihenfolge „gebrochen“ ist (d. h. das Array geht von einem höheren Wert zu einem niedrigeren Wert).
Wenn kein Pivot gefunden wird, bedeutet dies, dass das Array nicht gedreht wurde und wir eine reguläre binäre Suche durchführen können.


  
  
  Wie der Algorithmus funktioniert


Für ein Array wie [4, 5, 6, 1, 2, 3]:

• Der Pivot befindet sich bei Index 2 (6 ist der größte, gefolgt von 1, dem kleinsten).
• Wir verwenden diesen Pivot, um das Array in zwei Teile zu teilen: [4, 5, 6] und [1, 2, 3].
• Wenn das Ziel größer oder gleich dem ersten Element ist (in diesem Fall 4), durchsuchen wir die linke Hälfte. Ansonsten suchen wir die rechte Hälfte.

Diese Methode stellt sicher, dass wir effizient suchen und eine Zeitkomplexität von O(log n) erreichen, ähnlich einer standardmäßigen binären Suche.

Abschluss

Gedrehte sortierte Arrays sind eine häufige Frage in Vorstellungsgesprächen und eine nützliche Herausforderung, um Ihr Verständnis der binären Suche zu vertiefen. Indem wir den Pivot finden und unsere binäre Suche entsprechend anpassen, können wir das Array effizient in logarithmischer Zeit durchsuchen.

Wenn Sie diesen Artikel hilfreich fanden, können Sie sich gerne mit mir auf LinkedIn vernetzen oder Ihre Gedanken in den Kommentaren teilen! Viel Spaß beim Codieren!