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 gefunden 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äre Suche:

   • 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 die mittlere Elementanzahl[mid] kleiner als das Ziel ist, verschieben Sie den Startindex si auf Mitte 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äre Suche:

   • 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. Rückgabeergebnis:

   • 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  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  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
    }
}