Python - Suchalgorithmen
Die Suche ist eine sehr grundlegende Notwendigkeit, wenn Sie Daten in verschiedenen Datenstrukturen speichern. Der einfachste Ansatz besteht darin, jedes Element in der Datenstruktur zu durchsuchen und es mit dem gesuchten Wert abzugleichen. Dies wird als lineare Suche bezeichnet. Es ist ineffizient und wird nur selten verwendet. Wenn Sie jedoch ein Programm dafür erstellen, erhalten Sie eine Vorstellung davon, wie wir einige erweiterte Suchalgorithmen implementieren können.
Lineare Suche
Bei dieser Art der Suche wird nacheinander eine Suche nach allen Elementen durchgeführt. Jedes Element wird überprüft, und wenn eine Übereinstimmung gefunden wird, wird dieses bestimmte Element zurückgegeben, andernfalls wird die Suche bis zum Ende der Datenstruktur fortgesetzt.
def linear_search(values, search_for):
search_at = 0
search_res = False
# Match the value with each data element
while search_at < len(values) and search_res is False:
if values[search_at] == search_for:
search_res = True
else:
search_at = search_at + 1
return search_res
l = [64, 34, 25, 12, 22, 11, 90]
print(linear_search(l, 12))
print(linear_search(l, 91))
Wenn der obige Code ausgeführt wird, wird das folgende Ergebnis erzeugt:
True
False
Interpolationssuche
Dieser Suchalgorithmus arbeitet an der Prüfposition des erforderlichen Werts. Damit dieser Algorithmus ordnungsgemäß funktioniert, sollte die Datenerfassung sortiert und gleichmäßig verteilt sein. Anfänglich ist die Sondenposition die Position des mittigsten Elements der Sammlung. Wenn eine Übereinstimmung auftritt, wird der Index des Elements zurückgegeben. Wenn das mittlere Element größer als das Element ist, wird die Sondenposition erneut im Unterarray rechts vom mittleren Element berechnet. Andernfalls wird das Element im Subarray links vom mittleren Element gesucht. Dieser Prozess wird auch auf dem Subarray fortgesetzt, bis die Größe des Subarrays auf Null reduziert ist.
Es gibt eine spezielle Formel zur Berechnung der mittleren Position, die im folgenden Programm angegeben ist.
def intpolsearch(values,x ):
idx0 = 0
idxn = (len(values) - 1)
while idx0 <= idxn and x >= values[idx0] and x <= values[idxn]:
# Find the mid point
mid = idx0 +\
int(((float(idxn - idx0)/( values[idxn] - values[idx0]))
* ( x - values[idx0])))
# Compare the value at mid point with search value
if values[mid] == x:
return "Found "+str(x)+" at index "+str(mid)
if values[mid] < x:
idx0 = mid + 1
return "Searched element not in the list"
l = [2, 6, 11, 19, 27, 31, 45, 121]
print(intpolsearch(l, 2))
Wenn der obige Code ausgeführt wird, wird das folgende Ergebnis erzeugt:
Found 2 at index 0