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.
Benutzeravatar
praying_mantis
User
Beiträge: 4
Registriert: Samstag 18. März 2006, 14:05

Problem bei rekursiver Implementation der Biären Suche

Beitragvon praying_mantis » 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)
Benutzeravatar
Joghurt
User
Beiträge: 877
Registriert: Dienstag 15. Februar 2005, 15:07

Beitragvon Joghurt » 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

Beitragvon praying_mantis » 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:

Wer ist online?

Mitglieder in diesem Forum: Bing [Bot]