Sequentielle Suche versus Binäre Suche¶
Python bietet einige vorprogrammierte Suchmethoden auf Listen. Wir werden hier zwei unterschiedliche Suchstrategien selbst implementieren.
Zuerst implementieren wir eine Funktion sequential_search. Dabei beginnen wir die Suche an einem Ende der Liste und gehen dann Schritt für Schritt alle Elemente der Liste durch. Dabei wird jeweils geprüft ob der zu suchende Wert dem aktuellen Element entspricht und folglich in der Liste vorkommt.
Die zweite Funktion binary_search setzt eine sortierte Liste voraus. Dadurch lässt sich der Suchbereich schnell halbieren indem man nachsieht, welcher Wert in der Mitte der Liste zu finden ist.
Zur Vorbereitung implemetieren wir eine Funtion simple_data_generatordie uns eine einfache Liste der Länge n erzeugt. Damit lässt sich leicht überpfrüfen, ob unsere Suchalgorithmen korrekt arbeiten. Wir speichern in der Liste die Zahlen von $0$ bis $n-1$, so dass der Index mit dem Eintrag in der Liste übereinstimmt.
def simple_data_generator(n):
pass # Durch die Implementierung zu ersetzen!
simple_data = simple_data_generator(10)
print( simple_data)
None
Nun werden wir eine Funktion sequential_search implementieren, die als ersten Parameter eine Liste list und als zweiten Parameter einen Wert val erwartet. Der Rückgabewert der Funktion soll der erste Index sein bei dem val in der Liste list gefunden wird. Falls der Wert in der Liste nicht vorkommt soll None zurückgegeben werden.
def sequential_search(list, val):
pass # Durch die Implementierung zu ersetzen!
index = sequential_search(simple_data,10)
print(index)
None
def binary_search(list, val):
pass # Durch die Implementierung zu ersetzen!
index = binary_search(simple_data, 13)
print(index)
None
Rekursive Implementierung¶
Die obige Implementierung bezeichnet man als eine iterative Lösung. Man kann die Binäre Suche jedoch auch rekursiv implementieren. Hierzu implementieren wir eine Funktion binary_recursive(list,low,high,val) die ausser der zu durchsuchenden Liste und dem gesuchten Wert noch die Parameter low and high enthält. Damit kann die Suche in der Liste auf den Bereich zwischen low und high begrenzt werden. Die Funktion kann sich somit selbst auf einem Unterbereich der Liste aufrufen.
Das Prinzip rekursiver Algorithmen hat folgende Stuktur:
if (problem_klein_genug):
nicht_rekusiver_Zweig
else:
rekursiver_Zweig
def binary_recursive(list, low, high, val):
pass # Durch die Implementierung zu ersetzen!
print( binary_recursive( simple_data, 0, len(simple_data)-1, 1) )
None
Bermerkung zum "=" Operator bei Listen!¶
Wir wollen in diesem Beispiel sehen, wie sich Listen verhalten wenn wir den Zuweisungsoperator = verwenden.
x = 1
y = x
y = 42
print("y =", y, ", x = ", x)
pass # Hier folgt eine equivalente Implementierung für Listen
y = 42 , x = 1