Das Arbeiten mit sortierten Listen kann manchmal etwas schwierig sein. Sie müssen die Reihenfolge der Liste nach jedem Einfügen beibehalten und effizient nach Elementen darin suchen. Die binäre Suche ist ein leistungsstarker Algorithmus zum Suchen in einer sortierten Liste. Die Implementierung von Grund auf ist zwar nicht allzu schwierig, kann aber zeitaufwändig sein. Glücklicherweise bietet Python das Modul „bisect“, das den Umgang mit sortierten Listen erheblich erleichtert.

Was ist binäre Suche?

Die binäre Suche ist ein Algorithmus, der die Position eines Zielwerts innerhalb eines sortierten Arrays findet. Stellen Sie sich vor, Sie suchen in einem Telefonbuch nach einem Namen. Anstatt mit der ersten Seite zu beginnen, beginnen Sie wahrscheinlich in der Mitte des Buches und entscheiden, ob Sie in der ersten oder zweiten Hälfte weitersuchen möchten, je nachdem, ob der Name alphabetisch größer oder kleiner als der in der Mitte ist. Die binäre Suche funktioniert auf ähnliche Weise: Sie beginnt mit zwei Zeigern, einem am Anfang und einem am Ende der Liste. Anschließend wird das mittlere Element berechnet und mit dem Ziel verglichen.

Das bisect-Modul: Vereinfachung sortierter Listenoperationen

Während die binäre Suche effektiv ist, kann es mühsam sein, die Implementierung jedes Mal neu zu schreiben. Aber was wäre, wenn Sie dieselben Vorgänge mit nur einer Codezeile ausführen könnten? Hier kommt das Python-Modul „bisect“ ins Spiel. Bisect ist Teil der Standardbibliothek von Python und hilft Ihnen, eine sortierte Liste zu verwalten, ohne sie nach jedem Einfügen sortieren zu müssen. Dies geschieht mithilfe eines einfachen Halbierungsalgorithmus.

Das Bisect-Modul bietet zwei Schlüsselfunktionen: Bisect und Insort. Die bisect-Funktion findet den Index, an dem ein Element eingefügt werden soll, um die Liste sortiert zu halten, während insort das Element in die Liste einfügt und dabei seine sortierte Reihenfolge beibehält.

Verwendung des Bisect-Moduls: Ein praktisches Beispiel

Beginnen wir mit dem Importieren des Moduls:

import bisect

Beispiel 1: Einfügen einer Zahl in eine sortierte Liste

Angenommen, wir haben eine sortierte Liste von Zahlen:

data = [1, 3, 5, 6, 8]

Um eine neue Nummer einzufügen und dabei die Liste sortiert zu halten, verwenden Sie einfach:

bisect.insort(data, 7)

Nachdem dieser Code ausgeführt wurde, sehen die Daten folgendermaßen aus:

[1, 3, 5, 6, 7, 8]

Beispiel 2: Finden des Einfügepunkts

Was wäre, wenn Sie nur herausfinden möchten, wo eine Zahl eingefügt würde, ohne sie tatsächlich einzufügen? Sie können die Funktionen bisect_left oder bisect_right verwenden:

index = bisect.bisect_left(data, 4)
print(index)  # Output: 2

Dies sagt uns, dass die Zahl 4 an Index 2 eingefügt werden sollte, um die Liste sortiert zu halten.

Beispiel 3: Beibehalten der sortierten Reihenfolge in einer dynamischen Liste

Angenommen, Sie verwalten eine dynamisch wachsende Liste und müssen Elemente einfügen und gleichzeitig sicherstellen, dass sie sortiert bleibt:

dynamic_data = []
for number in [10, 3, 7, 5, 8, 2]:
    bisect.insort(dynamic_data, number)
    print(dynamic_data)

Dies gibt die Liste bei jedem Schritt aus, wenn Elemente eingefügt werden:

[10]
[3, 10]
[3, 7, 10]
[3, 5, 7, 10]
[3, 5, 7, 8, 10]
[2, 3, 5, 7, 8, 10]

Beispiel 4: Verwendung von bisect mit benutzerdefinierten Objekten

Angenommen, Sie haben eine Liste benutzerdefinierter Objekte, z. B. Tupel, und möchten diese basierend auf einem bestimmten Kriterium einfügen:

items = [(1, 'apple'), (3, 'cherry'), (5, 'date')]
bisect.insort(items, (2, 'banana'))
print(items)  # Output: [(1, 'apple'), (2, 'banana'), (3, 'cherry'), (5, 'date')]

Oder Sie möchten möglicherweise basierend auf dem zweiten Element jedes Tupels einfügen:

items = [('a', 10), ('b', 20), ('c', 30)]
bisect.insort(items, ('d', 25), key=lambda x: x[1])
print(items)  # Output: [('a', 10), ('b', 20), ('d', 25), ('c', 30)]

bisect in Aktion: Auf der Suche nach Wörtern

Das Halbierungsmodul ist nicht auf Zahlen beschränkt; Es kann auch nützlich sein, um in Listen mit Zeichenfolgen, Tupeln, Zeichen usw. zu suchen.
Um beispielsweise ein Wort in einer sortierten Liste zu finden:

def searchWord(dictionary, target):
    return bisect.bisect_left(dictionary, target)


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'guitar', 'happiness', 'ice', 'joke']
target = 'guitar'

Oder um das erste Wort in einer Wortgruppe mit einem bestimmten Präfix zu finden:

def searchPrefix(dictionary, prefix):
    return bisect.bisect_left(dictionary, prefix), bisect.bisect_right(dictionary, prefix   'z') # adding 'z' to the prefix to get the last word starting with the prefix
# bisect_rigth function will be discussed in a moment


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'generator', 'genetic', 'genius', 'gentlemen', 'guitar', 'happiness', 'ice', 'joke']
prefix = 'gen'

Beachten Sie jedoch, dass bisect_left den Index zurückgibt, an dem das Ziel eingefügt werden soll, und nicht, ob das Ziel in der Liste vorhanden ist.

Varianten von halbieren und insortieren

Das Modul enthält auch rechtsseitige Varianten: bisect_right und insort_right. Diese Funktionen geben den Index ganz rechts zurück, an dem ein Element eingefügt werden soll, wenn es bereits in der Liste vorhanden ist. Bisect_right gibt beispielsweise den Index des ersten Elements zurück, das größer als das Ziel ist, wenn sich das Ziel in der Liste befindet, während insort_right das Element an dieser Position einfügt.

halbieren Under the Hood

Die Stärke des Bisect-Moduls liegt in seiner effizienten Implementierung des binären Suchalgorithmus. Wenn Sie beispielsweise bisect.bisect_left aufrufen, führt die Funktion im Wesentlichen eine binäre Suche in der Liste durch, um den richtigen Einfügepunkt für das neue Element zu ermitteln.

So funktioniert es unter der Haube:

1. Initialisierung: Die Funktion beginnt mit zwei Zeigern, lo und hi, die die untere und obere Grenze des Suchbereichs innerhalb der Liste darstellen. Zunächst wird lo auf den Anfang der Liste (Index 0) und hi auf das Ende der Liste gesetzt (Index entspricht der Länge der Liste). Sie können aber auch benutzerdefinierte Lo- und Hi-Werte angeben, um innerhalb eines bestimmten Bereichs der Liste zu suchen.

2. Bisection: Innerhalb einer Schleife berechnet die Funktion den Mittelpunkt (mid) zwischen lo und hi. Anschließend wird der Wert in der Mitte mit dem Zielwert verglichen, den Sie einfügen möchten.

3. Vergleich:

* If the target is less than or equal to the value at `mid`, the upper bound (`hi`) is moved to `mid`.
* If the target is greater, the lower bound (`lo`) is moved to `mid   1`.

1. Beendigung: Dieser Vorgang wird fortgesetzt, wobei der Suchbereich jedes Mal halbiert wird, bis lo gleich hi ist. An dieser Stelle stellt lo (oder hi) den richtigen Index dar, an dem das Ziel eingefügt werden sollte, um die sortierte Reihenfolge der Liste beizubehalten.

2. Einfügung: Bei der Insort-Funktion wird das Ziel an dieser Position in die Liste eingefügt, sobald mit bisect_left der richtige Index gefunden wurde.

Dieser Ansatz stellt sicher, dass der Einfügungsprozess effizient ist, mit einer zeitlichen Komplexität von O(log n) für die Suche und O(n) für die Einfügung aufgrund der Listenverschiebungsoperation. Dies ist deutlich effizienter als das Sortieren der Liste nach jedem Einfügen, insbesondere bei großen Datensätzen.

bisect_left-Codebeispiel:

    if lo 



insort_left-Codebeispiel:


def insort_left(a, x, lo=0, hi=None, *, key=None):

    if key is None:
        lo = bisect_left(a, x, lo, hi)
    else:
        lo = bisect_left(a, key(x), lo, hi, key=key)
    a.insert(lo, x)





  
  
  Abschluss


Das Bisect-Modul macht die Arbeit mit sortierten Listen einfach und effizient. Wenn Sie das nächste Mal eine binäre Suche durchführen oder Elemente in eine sortierte Liste einfügen müssen, denken Sie an das Bisect-Modul und sparen Sie sich Zeit und Mühe.