Wie kann ich eine binäre Suche in Python effizient implementieren, um das Vorhandensein von Elementen zu überprüfen?

Binäre Suche (Halo-Suche) in Python

Python bietet Bibliotheksfunktionen zur Implementierung der binären Suche (auch binäre Suche genannt). Wird zum Suchen verwendet Elemente in einer sortierten Liste oder einem Tupel. Diese Funktionen geben jedoch weiterhin eine Position zurück, wenn das Element nicht gefunden wird.

Um dieses Problem zu lösen und nur zu erkennen, ob das Element vorhanden ist, besteht eine Möglichkeit darin, die Funktion bisect.bisect_left() zu verwenden, um die Einfügeposition zu finden und dann zu prüfen, ob das Element an dieser Position mit dem Zielelement übereinstimmt . Dies kann jedoch mühsam sein und erfordert außerdem eine Überprüfung der Grenzen, wenn die Zahl größer als die größte Zahl in der Liste ist.

Aufgrund des Speicherverbrauchs wird in der Frage alternativ ein Wörterbuch vorgeschlagen. Dies kann jedoch etwa den doppelten Speicherbedarf erfordern.

Daher kann dieses Problem durch die Implementierung einer binären Suche mit benutzerdefiniertem Code gelöst werden:

from bisect import bisect_left

def binary_search(a, x, lo=0, hi=None):
    if hi is None: hi = len(a)
    pos = bisect_left(a, x, lo, hi)                 # find insertion position
    return pos if pos != hi and a[pos] == x else -1  # don't walk off the end

Diese Funktion verwendet die Funktion bisect_left(), um die Einfügeposition zu finden, die die Position von angibt das Zielelement, falls es vorhanden ist, oder eine Position angeben, die außerhalb des Bereichs liegt, wenn es nicht vorhanden ist. Sie können feststellen, ob das Zielelement vorhanden ist, indem Sie prüfen, ob das Element an dieser Position mit dem Zielelement übereinstimmt.

Das obige ist der detaillierte Inhalt vonWie kann ich eine binäre Suche in Python effizient implementieren, um das Vorhandensein von Elementen zu überprüfen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!