Python Binäre Suche
Python3-BeispieleDie binäre Suche ist ein Suchalgorithmus zum Finden eines bestimmten Elements in einem sortierten Array. Der Suchprozess beginnt beim mittleren Element des Arrays. Wenn das mittlere Element zufällig das gesuchte Element ist, endet der Suchprozess. Wenn ein bestimmtes Element größer oder kleiner als das mittlere Element ist, wird die Suche in der Hälfte des Arrays fortgesetzt, die größer oder kleiner als das mittlere Element ist, und wie am Anfang beginnt der Vergleich beim mittleren Element. Wenn das Array bei einem Schritt leer wird, bedeutet das, dass das Element nicht gefunden wurde. Dieser Suchalgorithmus halbiert den Suchbereich bei jedem Vergleich.
Beispiel: Rekursion
# Gibt den Index von x in arr zurück oder -1, wenn x nicht vorhanden ist
def binarySearch (arr, l, r, x):
# Grundlegende Prüfung
if r >= l:
mid = int(l + (r - l)/2)
# Das Element befindet sich genau an der mittleren Position
if arr[mid] == x:
return mid
# Wenn das Element kleiner als das Element an der mittleren Position ist, müssen nur die Elemente auf der linken Seite verglichen werden
elif arr[mid] > x:
return binarySearch(arr, l, mid-1, x)
# Wenn das Element größer als das Element an der mittleren Position ist, müssen nur die Elemente auf der rechten Seite verglichen werden
else:
return binarySearch(arr, mid+1, r, x)
else:
# Nicht gefunden
return -1
# Testarray
arr = [ 2, 3, 4, 10, 40 ]
x = 10
# Funktionsaufruf
result = binarySearch(arr, 0, len(arr)-1, x)
if result != -1:
print ("Der Index des Elements im Array ist %d" % result )
else:
print ("Das Element ist nicht im Array")
Das Ausführen des obigen Codes erzeugt die folgende Ausgabe:
元素在数组中的索引为 3Andere Erweiterungen