Binäre Suche

[cz3kit]

Hi, ich versuche hier grade die Binäre suche zu programmieren, rekursiv, aber irgendwie will das nich ganz und ich weiß nicht w mein denkfehler sein könnte. Würde mich über tipps freuen.

Code: Alles auswählen

def binary(s, mylist, l, r):
   
   # l ist 0 also das erste Element in der Liste
   # und r ist das letzte element
    if l == r:
        return "Kein Element vorhanden"

   # m soll die mitte der liste sein
    m = (l + r)/ 2
    # wenn das Element an der Stelle m gleich dem Suchbegriff ist, soll
    # der das zurückgeben
    if mylist[m] == s:
        return mylist[m]
    # falls nicht
    else:
       # und das element[m] größer ist als der suchbegriff wird die funktion 
       # erneut aufgerufen und diesmal soll mylist vom ersten elemnt bis
       # zum mittleren Element - 1
        if mylist[m] > s:
            binary(s, mylist, l, m - 1)
            return mylist
        # wenn hier das element[m] kleiner ist als der suchbegriff wird die
        # funktion ebenfalls erneut aufgerufen, aber diesmal soll die liste 
        # von dem element[m] +1 bis zum letzten element das ganze 
        # durchführen
        elif mylist[m] < s:
            binary(s, mylist, m + 1, r)
            return mylist

ich würde das ganze erst mal mit einer liste machen die mit int gefüllt ist, damit mir klar was sache ist

Würde mich über Hilfe freuen

[BlackJack]

@cz3kit: Du musst das Ergebnis der binären Suche zurückgeben und nicht, wie in zwei Fällen die Liste.

Wobei man das nicht selber programmieren muss, es gibt schon das Modul `bisect` in der Standardbibliothek.

[EyDu]

Und den IndentationError wirst du durch korrekte Einrückung los

Den Teil im else-Abschnitt kannst du übrigens durch "elif" viel besser darstellen.

[cz3kit]

hoppla das return mylist hab ich vergessen rauszunehmen das gehört bei der dritten if bedingung nicht hin danach auch nicht. Ich hba kein IntendationError also bie mir ist das schon richtig eingerückt, aber er gibt mir immer None zurück und cih weiß nicht so recht warum.

@BlackJack aber mach ich das nicht mit der ersten if-Bedingung?

[EyDu]

Das return bezieht sich nur auf den aktuellen Funktionsaufruf. Aus den

Code: Alles auswählen

binary(s, mylist, l, m - 1)
return mylist

muss also ein

Code: Alles auswählen

return binary(s, mylist, l, m-1)

werden. Für den anderen Aufruf natürlich entsprechend.

Dann gibt es auch kein None mehr.

[cz3kit]

Also das sieht gerade so aus

Code: Alles auswählen

def binary(s, mylist, l, r):

    if l == r:
        return "kein Element vorhanden"

    m = (l + r)/ 2
    if mylist[m] == s:
        return mylist[m]

    elif mylist[m] > s:
        binary(s, mylist, l, m-1)
    elif mylist[m] < s:
        binary(s, mylist, m+1, r)

aber dennoch bekomme ich None, was ich nicht so ganz verstehe

[Leonidas]

Weil in den zwei Zweigen die ``return``s immer noch fehlen.

[EyDu]

Das liegt an dem l==r.

Code: Alles auswählen

def binary(s, mylist, l=None, r=None):
    if not mylist:
        return None
    
    if l is None:
         l = 0
    
    if r is None:
       r = len(mylist)-1

    m = (l + r)/ 2

    if mylist[m] == s:
        return m
    elif l==r:
        return None
    elif mylist[m] > s:
        return binary(s, mylist, l, m - 1)
    elif mylist[m] < s:
        return binary(s, mylist, m + 1, r)

Edit: hatte die -1 vergessen.

[cz3kit]

oO oh man -.- naja oke ich versteh jetzt den fehler ich danke euch