Die Webseiten der Fachschaft Informatik am ERG Saalfeld

binäre Suche

Es soll in einer sortierten Liste von Elementen ein Element gesucht werden. Es soll eine binäre Suche durchgeführt werden und diese Suche wird rekursiv implementiert.
 

Programm

from random import randint

feld=[]

# rekursive Suche auf dem Feld feld
# feld ist dabei eine globale Variable
def suche_rekursiv(suchwert, anfang, ende):
    mitte = (anfang + ende) // 2
    if feld[mitte] == suchwert:
        ergebnis = mitte
    elif ende < anfang:
        ergebnis = -1           # -1 = keine Stelle gefunden
    elif feld[mitte] < suchwert:
        ergebnis = suche_rekursiv(suchwert, mitte+1, ende)
    else:                   #   feld[mitte] > suchwert:
        ergebnis = suche_rekursiv(suchwert, anfang, mitte-1)
    return ergebnis

for i in range(120):
    feld.append(randint(1,100))

feld.sort()

for element in feld:
    print(element, end = ' ')
print('\n')

suchwert = 10

fundstelle = suche_rekursiv(suchwert, 0, len(feld)-1)

if fundstelle == -1:
    print('Der Suchwert ', suchwert, ' wurde nicht im Feld gefunden.')
else:
    print('Fundstelle fuer den Suchwert ', suchwert, ' ist die Stelle ', fundstelle, '.')

Der Aufruf sah bei mir so aus:

Aufgaben

1. Bringen Sie das Programm zum Laufen.
2. Kommentieren Sie das Programm ausführlich!
3. Geben Sie die Abbruchbedingung für den rekursiven Aufruf als Kommentar im Quelltext an.
4. Geben Sie den bzw. die rekursiven Aufrufe als Kommentar im Quelltext an.
5. Erläutern Sie anhand dieses Screenshots, dass die Zählung für die Fundstelle bei 0 beginnt.
6. Finden Sie heraus, wie viel Vergleiche (bzw. wie viel Aufrufe von suche_rekursiv) zum Finden der 10 im Screenshot nötig waren. ("Trockentest")     Feld als Textdatei
7. Welche Zeitkomplexität hat diese Suche? Begründen Sie!
8. Überprüfen Sie durch weitere Tests, ob bei mehrfachen Auftreten des Elements die Fundstelle immer das erste Auftreten des Elements ist.
9. Angenommen, die Suche in dem Feld von 120 Elementen dauert 35 ms. Wie lange dauert es mit diesem Programm ein Feld von 500000 Elementen zu durchsuchen?

zurück