Problem bei rekursiver Implementation der Biären Suche

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Benutzeravatar
praying_mantis
User
Beiträge: 4
Registriert: Samstag 18. März 2006, 14:05

Montag 21. August 2006, 11:44

Hallo Leute
Ich habe folgendes Problem:
Nachdem ich den Algorithmus zur Binären Suche erstmal iterativ gelöst habe wollte ich auch eine rekursive Lösung finden. Doch doch nach jedem Aufruf der rekursiven Variante bekomme ich als Rückgabewert None. Ich finde einfach den Fehler nicht. Ich hoffe ihr könnt mir helfen

iterative Lösung

Code: Alles auswählen

def binSearch(s, k, l, r):
    while l<=r:
        c = (l+r)/2
        if s[c]==k:
            return True
        elif s[c]>k:
            r = c - 1
        elif s[c]<k:
            l = c + 1
    return False
rekursive Lösung

Code: Alles auswählen

def rekBinSearch(s, k, l, r):
    c = (l+r)/2
    if l>r:
        return False
    else:
        if s[c]==k:
            return True
        elif s[c]>k:
            rekBinSearch(s,k,l,c-1)
        elif s[c]<k:
            rekBinSearch(s,k,c+1,r)
Joghurt
User
Beiträge: 877
Registriert: Dienstag 15. Februar 2005, 15:07

Montag 21. August 2006, 12:15

Du musst das Ergebnis des rekursiven Aufrufs natürlich auch wieder zurückgeben:

Code: Alles auswählen

def rekBinSearch(s, k, l, r):
    c = (l+r)/2
    if l > r:
        return False
    else:
        if s[c] == k:
            return True
        elif s[c]>k:
            return rekBinSearch(s,k,l,c-1)
        elif s[c]<k:
            return rekBinSearch(s,k,c+1,r)
Benutzeravatar
praying_mantis
User
Beiträge: 4
Registriert: Samstag 18. März 2006, 14:05

Montag 21. August 2006, 15:57

Danke für die schnelle Antwort :D
Ich habe total vergessen das ich das Ergebnis noch zurückliefern muss :oops:
Antworten