Wie verwende ich Advanced Binary Scarch?

Warum und wie?

Während ich die Frage zu Leetcode gelöst habe, die besagt, dass in einem gegebenen Array von ganzen Zahlen, die in nicht absteigender Reihenfolge sortiert sind, die Start- und Endposition eines bestimmten Zielwerts ermittelt werden soll. Daher war es unmöglich, den Anfang und das Ende eines Zielelements in einem Array mit einem einfachen binären Scan zurückzugeben, da nur der Index zurückgegeben wird, an dem das erste Zielelement gefunden wurde, bei dem es sich um den Anfang, das Ende oder die Mitte dieses Elements handeln kann. Also verwenden wir Double Binary Scarch und hier erfahren Sie, wie es geht ...

Ansatz

1. Erste Binärsuche:

   • Führen Sie eine binäre Suche durch, um das letzte Vorkommen des Ziels zu finden.
   • Beginnen Sie mit si (Startindex) bei 0 und ei (Endindex) bei nums.length - 1.
   • Wenn das mittlere Element nums[mid] kleiner als das Ziel ist, verschieben Sie den Startindex si auf mid + 1, um in der rechten Hälfte zu suchen.
   • Wenn es größer als das Ziel ist, verschieben Sie den Endindex ei auf Mitte - 1, um in der linken Hälfte zu suchen.
   • Wenn nums[mid] dem Ziel entspricht, setzen Sie res[1] auf mid (das aktuelle Ende des Bereichs) und suchen Sie weiter in der rechten Hälfte (si = mid + 1), um das letzte Vorkommen zu finden.

2. Zweite Binärsuche:

   • Führen Sie eine weitere binäre Suche durch, um das erste Vorkommen des Ziels zu finden.
   • Si auf 0 und ei auf nums.length - 1 zurücksetzen.
   • Verfolgen Sie einen ähnlichen Ansatz wie zuvor, aber wenn nums[mid] dem Ziel entspricht, setzen Sie res[0] auf mid (den aktuellen Anfang des Bereichs) und setzen Sie die Suche in der linken Hälfte (ei = mid - 1) fort Finden Sie das erste Vorkommen.

3. Ergebnis zurückgeben:

   • Das Ergebnisarray res enthält den Start- und Endindex des Zielwerts.

Komplexität

• Zeitkomplexität:

  • Die binäre Suche nach dem ersten und letzten Vorkommen dauert jeweils O(log n) Zeit. Da wir zwei binäre Suchen durchführen, beträgt die Gesamtzeitkomplexität O(log n).

• Weltraumkomplexität:

  • O(1), da wir eine feste Menge an zusätzlichem Platz für Variablen verwenden.

Code

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int ei = nums.length - 1;
        int si = 0;
        int[] res = {-1, -1};  // Initialize result array

        // First binary search to find the last occurrence
        while (si <= ei) {
            int mid = si + (ei - si) / 2;
            if (target < nums[mid]) {
                ei = mid - 1;
            } else if (target > nums[mid]) {
                si = mid + 1;
            } else {
                res[1] = mid;  // Update end index
                si = mid + 1;  // Search in the right half
            }
        }

        // Reset the pointers for the second binary search
        si = 0;
        ei = nums.length - 1;

        // Second binary search to find the first occurrence
        while (si <= ei) {
            int mid = si + (ei - si) / 2;
            if (target < nums[mid]) {
                ei = mid - 1;
            } else if (target > nums[mid]) {
                si = mid + 1;
            } else {
                res[0] = mid;  // Update start index
                ei = mid - 1;  // Search in the left half
            }
        }

        return res;  // Return the result array
    }
}

Das obige ist der detaillierte Inhalt vonWie verwende ich Advanced Binary Scarch?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!