Binäre Suche in Python: Eine visuelle Einführung

Herzlich willkommen

In diesem Artikel erfahren Sie, wie der Algorithmus für die binäre Suche hinter den Kulissen funktioniert und wie Sie ihn in Python implementieren können.

Insbesondere lernen Sie:

  • Wie der Algorithmus hinter den Kulissen arbeitet, um ein Zielelement zu finden.
  • Wie die Python-Implementierung Zeile für Zeile funktioniert.
  • Warum es ein sehr effizienter Algorithmus im Vergleich zur linearen Suche ist.
  • Seine Vorteile und Anforderungen.

Lass uns anfangen! ✨

🔹 Einführung in die binäre Suche

Dieser Algorithmus wird verwendet, um ein Element in einer geordneten Reihenfolge zu finden (z. B. eine Liste, ein Tupel oder eine Zeichenfolge).

Bedarf

Um den binären Suchalgorithmus auf eine Sequenz anzuwenden, muss die Sequenz bereits in aufsteigender Reihenfolge sortiert werden. Andernfalls findet der Algorithmus nicht die richtige Antwort. Wenn ja, wird es rein zufällig sein.

💡 Tipp: Sie können die Sequenz sortieren, bevor Sie die binäre Suche mit einem Sortieralgorithmus anwenden, der Ihren Anforderungen entspricht.

Ein- und Ausgabe

Der Algorithmus (als Funktion implementiert) benötigt diese Daten:

  • Eine geordnete Folge von Elementen (zum Beispiel: Liste, Tupel, Zeichenfolge).
  • Das Zielelement, nach dem wir suchen.

Es gibt den Index des Elements zurück, nach dem Sie suchen, wenn es gefunden wurde. Wird das Element nicht gefunden, wird -1 zurückgegeben.

Effizienz

Es ist sehr effizient im Vergleich zur linearen Suche (Suche nach einem Element nach dem anderen, beginnend mit dem ersten), da wir bei jedem Schritt die Hälfte der Liste "verwerfen" können.

Lassen Sie uns in diesen Algorithmus eintauchen.

🔸 Visuelle exemplarische Vorgehensweise

Wir werden den binären Suchalgorithmus auf diese Liste anwenden:

💡 Tipp: Beachten Sie, dass die Liste bereits sortiert ist. Es enthielt die Indizes als visuelle Referenz.

Tor

Wir wollen den Index der ganzen Zahl 67 finden .

Intervall

Stellen wir uns vor, wir sind der Algorithmus. Wie starten wir den Prozess?

Wir beginnen mit der Auswahl der beiden Grenzen des Intervalls, in dem wir suchen möchten. Wir möchten die gesamte Liste durchsuchen, also wählen wir Index 0als Untergrenze und Index 5als Obergrenze:

Mittleres Element

Jetzt müssen wir den Index des mittleren Elements in diesem Intervall finden. Dazu addieren wir die Untergrenze und die Obergrenze und dividieren das Ergebnis durch Ganzzahldivision durch 2.

In diesem Fall (0 + 5)//2liegt es 2daran, dass das Ergebnis von 5/2is 2.5und Integer Division den Dezimalteil abschneidet.

Das mittlere Element befindet sich also am Index 2 und das mittlere Element ist die Nummer 6 :

Vergleiche

Jetzt müssen wir das mittlere Element mit unserem Zielelement vergleichen, um zu sehen, was wir als nächstes tun müssen.

Wir fragen:

Entspricht das mittlere Element dem gesuchten Element?

6 == 67 # False

Nein, ist es nicht.

Also fragen wir:

Ist das mittlere Element größer als das gesuchte Element?

6 > 67 # False

Nein, ist es nicht.

So das mittlere Element kleiner als das Element , das wir suchen.

6 < 67 # True

Elemente verwerfen

Da die Liste bereits sortiert ist, sagt uns dies etwas äußerst Wichtiges. Es sagt uns, dass wir die untere Hälfte der Liste "verwerfen" können, weil wir wissen, dass alle Elemente, die vor dem mittleren Element stehen, kleiner sind als das Element, nach dem wir suchen, sodass unser Zielelement nicht vorhanden ist.

Neu starten - Wählen Sie die Grenzen

Was machen wir als Nächstes? Wir haben die Elemente verworfen und der Zyklus wird erneut wiederholt.

Wir müssen die Grenzen für das neue Intervall auswählen (siehe unten). Beachten Sie jedoch, dass die Obergrenze intakt bleibt und nur die Untergrenze geändert wird.

Dies liegt daran, dass sich das Element, nach dem wir suchen, möglicherweise in der oberen Hälfte der Liste befindet. Die Obergrenze bleibt erhalten und die Untergrenze wird geändert, um das Intervall auf ein Intervall zu "verkleinern", in dem unser Zielelement gefunden werden konnte.

💡 Tipp: Wenn das mittlere Element größer gewesen wäre als das gesuchte Element, wäre die Obergrenze geändert und die Untergrenze intakt geblieben. Auf diese Weise würden wir die obere Hälfte der Liste verwerfen und in der unteren Hälfte weiter suchen.

Mittleres Element

Jetzt müssen wir den Index des mittleren Elements finden, indem wir die Untergrenze zur Obergrenze addieren und das Ergebnis durch Ganzzahldivision durch 2 teilen.

Das Ergebnis von (3+5)//2ist 4, also befindet sich das mittlere Element am Index4 und das mittlere Element ist 67 .

Vergleiche

Wir fragen:

Entspricht das mittlere Element dem gesuchten Element?

67 == 67 # True

Ja ist es! Wir haben das Element also bei Index 4 gefunden . Der Wert 4 wird zurückgegeben und der Algorithmus wurde erfolgreich abgeschlossen.

💡 Tipp: Wenn das Element nicht gefunden worden wäre, wäre der Vorgang fortgesetzt worden, bis das Intervall nicht mehr gültig war. Wenn das Element nicht in der gesamten Liste gefunden worden wäre, wäre -1 zurückgegeben worden.

🔹 Code-exemplarische Vorgehensweise

Nachdem Sie nun eine visuelle Vorstellung davon haben, wie der Algorithmus hinter den Kulissen funktioniert, wollen wir uns mit der iterativen Python-Implementierung befassen, indem wir sie Zeile für Zeile analysieren:

def binary_search(data, elem): low = 0 high = len(data) - 1 while low  elem: high = middle - 1 else: low = middle + 1 return -1

Header

Hier haben wir den Funktionsheader:

def binary_search(data, elem):

Es braucht zwei Argumente:

  • Die geordnete Folge von Elementen (z. B. Liste, Tupel oder Zeichenfolge).
  • Das Element, das wir finden wollen.

Anfangsintervall

In der nächsten Zeile werden die anfänglichen unteren und oberen Grenzen festgelegt:

low = 0 high = len(data) - 1

Die anfängliche Untergrenze ist der Index 0und die anfängliche Obergrenze ist der letzte Index der Sequenz.

Schleife

Wir werden den Vorgang wiederholen, solange es ein gültiges Intervall gibt, während die Untergrenze kleiner oder gleich der Obergrenze ist.

while low <= high:

💡 Tipp: Denken Sie daran, dass die Grenzen Indizes sind.

Mittleres Element

Bei jeder Iteration müssen wir den Index des mittleren Elements finden. Dazu addieren wir die Unter- und Obergrenze und dividieren das Ergebnis durch Ganzzahldivision durch 2.

middle = (low + high)//2

💡 Tipp: Wir verwenden die Ganzzahldivision, wenn die Liste oder das Intervall eine gerade Anzahl von Elementen enthält. Wenn die Liste 6 Elemente hat zum Beispiel, und wir haben nicht ganzzahligen Division verwenden, middlewäre das Ergebnis (0 + 5)/2davon ist 2.5. Ein Index kann kein Float sein, daher kürzen wir den Dezimalteil, indem wir //das Element am Index verwenden und auswählen 2.

Vergleiche

Mit diesen Bedingungen (siehe unten) legen wir fest, was in Abhängigkeit vom Wert des mittleren Elements zu tun ist data[middle]. Wir vergleichen es mit dem Zielelement, das wir suchen.

if data[middle] == elem: return middle elif data[middle] > elem: high = middle - 1 else: low = middle + 1

Es gibt drei Möglichkeiten:

  • Wenn das mittlere Element dem gesuchten Element entspricht, geben wir den Index sofort zurück, da wir das Element gefunden haben.
if data[middle] == elem: return middle
  • Wenn das mittlere Element größer als das gesuchte Element ist, weisen wir die Obergrenze neu zu, da wir wissen, dass sich das Zielelement in der unteren Hälfte der Liste befindet.
elif data[middle] > elem: high = middle - 1
  • Andernfalls bleibt nur noch die Option, dass das mittlere Element kleiner als das gesuchte Element ist. Daher weisen wir die Untergrenze neu zu, da wir wissen, dass sich das Zielelement in der oberen Hälfte der Liste befindet.
else: low = middle + 1

Element nicht gefunden

Wenn die Schleife abgeschlossen ist, ohne das Element zu finden, wird der Wert -1 zurückgegeben.

return -1

und wir haben die endgültige Implementierung des binären Suchalgorithmus:

def binary_search(data, elem): low = 0 high = len(data) - 1 while low  elem: high = middle - 1 else: low = middle + 1 return -1

🔸 Sonderfälle

Dies sind einige besondere Fälle, die auftreten können, wenn Sie mit diesem Algorithmus arbeiten:

Wiederholte Elemente

Wenn das gesuchte Element in der Sequenz wiederholt wird, hängt der zurückgegebene Index von der Anzahl der Elemente und der Reihenfolge der Operationen ab, die der Algorithmus für die Sequenz ausführt.

>>> >>> b = [2, 2, 3, 6, 7, 7] >>> binary_search(b, 7) 4 

Element nicht gefunden

Wird das Element nicht gefunden, wird -1 zurückgegeben.

>>> b = [2, 2, 3, 6, 7, 7] >>> binary_search(b, 8) -1

Leere Sequenz

Wenn die Sequenz leer ist, wird -1 zurückgegeben.

>>> b = [] >>> binary_search(b, 8) -1

Unsortierte Sequenz

Wenn die Reihenfolge nicht sortiert ist, ist die Antwort nicht korrekt. Das Erhalten des richtigen Index ist ein reiner Zufall und kann auf die Reihenfolge der Elemente in der Sequenz und die Sequenz der vom Algorithmus ausgeführten Operationen zurückzuführen sein.

Dieses Beispiel liefert das richtige Ergebnis:

>>> b = [5, 7, 3, 0, -9, 2, 6] >>> binary_search(b, 6) 6

Aber dieser nicht:

>>> b = [5, 7, 3, 0, -9, 2, 10, 6] >>> binary_search(b, 6) -1

💡 Tipp: Überlegen Sie, warum das erste Beispiel das richtige Ergebnis liefert. Hinweis: Es ist reiner Zufall, dass die Reihenfolge der Elemente dazu führt, dass der Algorithmus den richtigen Index erreicht, aber der schrittweise Prozess wertet 0dann 2und schließlich aus 6. In diesem speziellen Fall wird für dieses bestimmte Element der richtige Index gefunden, auch wenn die Sequenz nicht sortiert ist.

🔹 Ein komplexeres Beispiel

Nachdem Sie mit dem Algorithmus und seiner Python-Implementierung besser vertraut sind, haben wir hier ein komplexeres Beispiel:

Wir möchten den Index des Elements 45 in dieser Liste mithilfe der binären Suche finden:

Erste Iteration

Die unteren und oberen Grenzen werden ausgewählt:

Das mittlere Element ( 26 ) ist ausgewählt:

Das mittlere Element ( 26 ) ist jedoch nicht das gesuchte Element, es ist kleiner als 45 :

Zweite Iteration

So können wir alle Elemente verwerfen, die kleiner als das mittlere Element sind, und neue Grenzen auswählen. Die neue Untergrenze ( 27 ) ist das Element, das sich unmittelbar rechts vom vorherigen mittleren Element befindet:

💡 Tipp: Denken Sie daran, dass die Liste bereits sortiert ist.

Das neue mittlere Element ( 30 ) wird ausgewählt:

Das mittlere Element ( 30 ) ist nicht das gesuchte Element, es ist kleiner als 45 :

Dritte Iteration

Wir können die Elemente verwerfen, die kleiner oder gleich 30 sind und noch nicht verworfen wurden. Die Untergrenze wird auf 32 aktualisiert :

Hier haben wir einen interessanten Fall: Das mittlere Element ist eine der Grenzen des aktuellen Intervalls, weil es (7+8)//2ist 7.

Das mittlere Element ( 32 ) ist nicht das gesuchte Element ( 45 ), es ist kleiner.

Vierte Iteration

Wir können die Elemente verwerfen, die kleiner oder gleich 32 sind und noch nicht verworfen wurden.

Hier haben wir einen weiteren sehr interessanten Fall: Das Intervall hat nur ein Element.

💡 Tipp: Dieses Intervall ist gültig, da wir diese Bedingung geschrieben haben while high <= low:, die Intervalle enthält, in denen der Index der Untergrenze gleich dem Index der Obergrenze ist.

Das mittlere Element ist das einzige Element im Intervall da (8+8)//2ist 8, so dass der Index des mittleren Elements 8 und das mittlere Element 45 .

Jetzt ist das mittlere Element das Element, nach dem wir suchen, 45 :

Der Wert 8 (der Index) wird also zurückgegeben:

>>> binary_search([1, 3, 7, 15, 26, 27, 30, 32, 45], 45) 8

🔸 Zusätzliche Übung

Wenn Sie zusätzliche Übung mit diesem Algorithmus wünschen, versuchen Sie zu erklären, wie der Algorithmus hinter den Kulissen funktioniert, wenn er auf diese Liste angewendet wird, um die Ganzzahl 90 zu finden :

[5, 8, 15, 26, 38, 56]
  • Was passiert Schritt für Schritt?
  • Welcher Wert wird zurückgegeben?
  • Ist das Element gefunden?

Ich hoffe wirklich, dass Ihnen mein Artikel gefallen hat und Sie ihn hilfreich fanden. Jetzt können Sie den binären Suchalgorithmus in Python implementieren. Schauen Sie sich meinen Online-Kurs "Python-Such- und Sortieralgorithmen: Ein praktischer Ansatz" an. Folge mir auf Twitter. ⭐️