Der binäre Suchalgorithmus

Die Liste halbieren

Der binäre Suchalgorithmus arbeitet, indem er die Liste zunächst sortiert (siehe Sortieralgorithmen) und dann das gesuchte Element mit dem Eintrag "in der Mitte" der sortierten Liste vergleicht. Ist er kleiner, wendet er das Verfahren rekursiv auf die Argumente links des mittleren Arguments an. Ist er größer, wendet er das Verfahren rekursiv auf die Argumente rechts des mittleren Arguments an. Das geschieht, bis das gesuchte Argument gefunden wird.

Idee

Algorithmus

def quicksort(liste):
   ...

def binaereSuche(gesuchteZahl, liste, indexVorsprung):
   if len(liste) == 0:
       print("Zahl nicht gefunden")
       return None
   if gesuchteZahl==liste[math.floor(len(liste)/2)]:
       return (math.floor(len(liste)/2)) + indexVorsprung
   elif gesuchteZahl < liste[math.floor(len(liste)/2)]:
       return binaereSuche(gesuchteZahl, liste[:math.floor(len(liste)/2)], indexVorsprung)
   else:
       return binaereSuche(gesuchteZahl, liste[math.floor(len(liste)/2)+1:], indexVorsprung+math.floor(len(liste)/2)+1)

Aufgabe 3

(a) Vergleiche auch diesen Algorithmus mit deinem Suchalgorithmus. In welchen Fällen ist dein Algorithmus deiner Meinung nach schneller als binaereSuche? In welchen ist er langsamer, oder ist es vielleicht sogar der gleiche Alogrithmus?

Anmerkung: Wenn Du Probleme mit diesem Algorithmus hast, führe ihn einmal von Hand an zwei oder drei Beispielen aus.

(b) Überprüfe deine Hypothese, indem Du die Laufzeit der beiden Algorithmen mit den Dir bekannten Methoden vergleichst.

(c) Vergleiche binaereSuche auch mit naiveSuche, wenn du das nicht schon implizit durch den Vergleich mit deinem Algorithmus gemacht hast. Was fällt dir auf?