Findet diese binäre Python-Suchfunktion das Element?

Binäre Suche (Bisektion) in Python

Die Feststellung, ob ein Element in einer sortierten Liste oder einem Tupel vorhanden ist, ist eine häufige Aufgabe in der Programmierung. Während Python das Modul „bisect“ für die binäre Suche bereitstellt, geben seine Funktionen „bisect_left“ und „bisect_right“ eine Position zurück, auch wenn das Element nicht gefunden wird. Um diesem Bedarf gerecht zu werden, wird eine Python-Implementierung der binären Suche eingeführt, die explizit einen booleschen Wert zurückgibt.

Vorgeschlagene Lösung

Die Funktion „binary_search“ verwendet eine sortierte Liste „a“. , ein zu suchendes Element „x“ und optionale Start- und Endpositionen „lo“ und „hi“ für den Suchbereich. Es verwendet die Funktion bisect_left aus dem Modul bisect, um den Einfügepunkt „pos“ für „x“ in der Liste „a“ zu lokalisieren.

Wenn „pos“ kleiner als „hi“ ist und das Element bei „pos ' gleich 'x' ist, dann wird 'x' gefunden und 'pos' wird als Index seiner Position in der Liste zurückgegeben. Wenn „pos“ jedoch das Ende der Liste erreicht (d. h. „pos“ entspricht „hi“), wird „x“ nicht gefunden und die Funktion gibt -1 zurück.

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

Beispielverwendung

Wenn beispielsweise eine sortierte Liste „a“ und ein zu suchendes Element „x“ vorhanden sind, kann die Funktion „binary_search“ verwendet werden als folgt:

result = binary_search(a, x)

if result == -1:
    print("Element not found")
else:
    print("Element found at index", result)

Diese prägnante Python-Funktion bietet eine praktische Möglichkeit, eine binäre Suche zur Überprüfung der Existenz von Elementen in sortierten Listen durchzuführen und dabei die Einfachheit und Effizienz der binären Suche beizubehalten.

Das obige ist der detaillierte Inhalt vonFindet diese binäre Python-Suchfunktion das Element?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!