So implementieren Sie die binäre Suche mit Python

Erstellen Sie zunächst eine Funktion namens „binary_search“: Übergeben Sie zwei Parameter, die Liste der Elemente und den Wert, den Sie suchen möchten.

def binary_search(_list, value):

Als nächstes definieren Sie die erforderlichen Variablen innerhalb der Funktion. Der Schlüssel zur Dichotomie besteht darin, von der Mitte der Liste nach beiden Seiten zu suchen (der Ausdruck ist möglicherweise nicht streng, aber das ist es, was er bedeutet). Intuition, definiere links, rechts, Mitte. Drei Variablen repräsentieren: den Startindex, den Endindex und den mittleren Index der Liste.

    left = 0   # 列表的起始索引
    right = len(_list)   # 列表的结束索引
    mid = int((left + right)/2)  # 采用此方法，通过四舍五入刚好可以定位到列表的中间位置

Der nächste Schritt besteht darin, den Schlüsselteil der binären Suche zu implementieren. Definieren Sie zunächst eine While-Schleife, damit die Suche reibungslos ablaufen kann. Es gibt drei Situationen:

1. _list[mid] == value: Der Zwischenwert ist zufällig der Wert, den wir finden müssen, also geben Sie einfach den entsprechenden Index direkt zurück.

2. _list[mid] > Wert: Der zu findende Wert befindet sich auf der linken Seite von mid, um den Suchbereich einzugrenzen.

3._list[mid] < value: Der zu findende Wert befindet sich auf der rechten Seite von mid, aktualisieren Sie den Wert von left auf mid und suchen Sie auf der rechten Seite von mid.

Aktualisieren Sie abschließend den Wert von mid, um die nächste Suchrunde zu starten, und verwenden Sie die while-else-Anweisung, um zu beurteilen, ob er nicht gefunden wird, und geben Sie einen Rückgabewert an.

    while left < right:
        if _list[mid] == value:
            return mid
        elif _list[mid] > value:
            right = mid
        else:
            left = mid
        mid = int((right + left)/2)
    else:
        return -1

Abschließend sind der vollständige Code und die Testlaufleistung wie folgt:

""" a demo realize binary search"""
 
 
def binary_search(_list, value):
    left = 0   # 列表的起始索引
    right = len(_list)   # 列表的结束索引
    mid = int((left + right)/2)  # 采用此方法，通过四舍五入刚好可以定位到列表的中间位置
    while left < right:
        if _list[mid] == value:
            return mid
        elif _list[mid] > value:
            right = mid
        else:
            left = mid
        mid = int((right + left)/2)
    else:
        return -1
 
 
index = "the index of value in the list: {}"
print(index.format(binary_search([1, 2, 3, 4, 5, 6, 7, 8, 9], 1)))

Laufergebnisse:

Wenn kein Wert gefunden werden kann:

Das obige ist der detaillierte Inhalt vonSo implementieren Sie die binäre Suche mit Python. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!