Binäre Suche || Python || Datenstrukturen und Algorithmen

Binäre Suche

Binäre Suche ist ein Algorithmus, der den Suchraum wiederholt in zwei Hälften teilt. Diese Suchtechnik folgt der Divide-and-Conquer-Strategie. Der Suchraum reduziert sich bei jeder Iteration immer auf die Hälfte, was zu einer zeitlichen Komplexität von O(log(n)) führt, wobei n die Anzahl der Elemente ist.

Bedingung: Arrays sollten sortiert sein, sie können aber auch auf monotone Funktionen angewendet werden, bei denen wir monoton steigende oder fallende finden müssen.

Es funktioniert, wenn wir den Suchraum in logarithmischer Zeit eingrenzen müssen.

Wir verwenden zwei Zeiger, links und rechts. Nehmen Sie den Durchschnitt von links und rechts, um das mittlere Element zu finden.

Jetzt prüfen wir, wohin wir unsere linken und rechten Zeiger je nach Bedingung bewegen sollen.

Im Wesentlichen sind drei Schritte erforderlich, um ein Problem zu lösen:

1. Vorverarbeitung: Sortieren Sie die Eingabe, wenn sie nicht sortiert ist.
2. Binäre Suche: Verwenden Sie zwei Zeiger und finden Sie die Mitte, um den Suchraum zu teilen, und wählen Sie dann entsprechend die richtige Hälfte aus.
3. Nachbearbeitung:Bestimmen Sie die Ausgabe.

Vorteile des binären Suchalgorithmus – Die binäre Suche ist bei großen Datenmengen schneller als die lineare Suche, da sie das Array jedes Mal halbiert, anstatt jedes Element einzeln zu überprüfen. Das macht es schneller und effizienter.

Einschränkungen: Die binäre Suche funktioniert nur bei sortierten Arrays, daher ist sie für kleine unsortierte Arrays nicht effizient, da das Sortieren zusätzliche Zeit in Anspruch nimmt. Es funktioniert auch nicht so gut wie die lineare Suche bei kleinen Suchen im Speicher.

Anwendungen: Es wird verwendet, um Elemente in einem sortierten Array mit O(log(n))-Zeitkomplexität zu suchen, und es kann auch verwendet werden, um das kleinste oder größte Element im Array zu finden.

Einfacher binärer Suchcode –

Code

def binarySearch(nums, target):
    if len(nums) == 0:
        return -1

    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    # End Condition: left > right
    return -1

33. Suche im gedrehten sortierten Array
Geben Sie bei gegebenen Array-Nummern nach der möglichen Drehung und einem ganzzahligen Ziel den Index des Ziels zurück, wenn es in Zahlen vorliegt, oder -1, wenn es nicht in Zahlen vorliegt.
Sie müssen einen Algorithmus mit einer Laufzeitkomplexität von O(log n) schreiben.
Beispiel 1:
Eingabe: Nums = [4,5,6,7,0,1,2], Ziel = 0
Ausgabe: 4

Beispiel 2:
Eingabe: Nums = [4,5,6,7,0,1,2], Ziel = 3
Ausgabe: -1

Beispiel 3:
Eingabe: Nums = [1], Ziel = 0
Ausgabe: -1

Code

def binarySearch(nums, target):
    if len(nums) == 0:
        return -1

    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    # End Condition: left > right
    return -1

1. Verwenden Sie zwei Zeiger, links und rechts, und iterieren Sie, bis sie sich überlappen.
2. Finden Sie das mittlere Element.
3. Da das Array sortiert, aber gedreht ist, können wir nicht einfach die linken oder rechten Elemente mit der Mitte vergleichen.
4. Bestimmen Sie zunächst, welcher Teil links oder rechts sortiert ist, indem Sie den mittleren Zeiger mit dem linken oder rechten Zeiger vergleichen.
5. Passen Sie die Zeiger basierend auf dieser Schlussfolgerung entsprechend an.

Zeitkomplexität – O(log(n)) da der Suchraum in jeder Iteration in zwei Hälften geteilt wird.
Raumkomplexität – O(1)

Monotonisch ansteigend

162. Peak-Element finden

Ein Spitzenelement ist ein Element, das unbedingt größer als seine Nachbarn ist.
Suchen Sie anhand eines 0-indizierten Ganzzahlarrays nums ein Spitzenelement und geben Sie seinen Index zurück. Wenn das Array mehrere Peaks enthält, geben Sie den Index zu einem der Peaks zurück.
Sie können sich vorstellen, dass nums[-1] = nums[n] = -∞. Mit anderen Worten: Ein Element wird immer als strikt größer als ein Nachbar außerhalb des Arrays betrachtet.
Sie müssen einen Algorithmus schreiben, der in O(log n) Zeit läuft.

Beispiel 1:
Eingabe: nums = [1,2,3,1]
Ausgabe: 2
Erläuterung: 3 ist ein Spitzenelement und Ihre Funktion sollte die Indexnummer 2 zurückgeben.
Beispiel 2:
Eingabe: nums = [1,2,1,3,5,6,4]
Ausgabe: 5
Erläuterung: Ihre Funktion kann entweder Index Nummer 1 zurückgeben, wenn das Spitzenelement 2 ist, oder Index Nummer 5, wenn das Spitzenelement 6 ist.

Code

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)-1

        while left <= right:

            mid = (left + right)//2
            print(f'left is {left},right is {right} and mid is {mid}')
            if nums[mid]==target:
                return mid

            if nums[mid] >= nums[left]:
                # if nums[mid]< target and target >= nums[left]:
                if nums[left] <= target < nums[mid]:
                    right = mid -1
                else:
                    left = mid +1
            else:
                # if nums[mid] < target and target <= nums[right]:
                if nums[mid] < target <= nums[right]:
                    left = mid +1
                else:
                    right = mid - 1

        return -1

1. Bei dieser Art von Problem müssen wir den Peak ermitteln, indem wir das linke oder rechte Element der Mitte vergleichen.
2. Dies hilft festzustellen, ob die Grafik einen Aufwärts- oder Abwärtstrend aufweist.
3. Um das Maximum zu finden, suchen Sie den ansteigenden Hang ab und erkunden Sie den richtigen Unterraum.
4. Um das Minimum zu finden, durchsuchen Sie den linken Unterraum

Zeitkomplexität – O(log(n)) da der Suchraum in jeder Iteration in zwei Hälften geteilt wird.
Raumkomplexität – O(1)

Das obige ist der detaillierte Inhalt vonBinäre Suche || Python || Datenstrukturen und Algorithmen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!