Python Bisektion Suche Übung

Question

Ich habe es seit einer Weile angeschaut und ich kann nicht sehen, was mit meiner Halbierung Suche falsch ist. Wenn ich es ausführe, heißt es 'RecursionError: maximale Rekursionstiefe im Vergleich überschritten'. Kann jemand einen Blick darauf werfen und sehen, was unten falsch ist? Vielen Dank!

#Write a function called in_bisect 
#that takes a sorted list and a target value 
#and returns the index 
#of the value in the list if it’s there 

def in_bisect(t, word): 

    if len(t) == 0: 
     return False 

    middle = len(t) // 2 

    if t[middle] == word: 
     return middle 

    elif t[middle] > word: 
     return in_bisect(t[:middle], word) 
    else: 
     return in_bisect(t[middle:], word) 


if __name__ == "__main__": 
    fruits = ['apple', 'banana', 'kiwi', 'peach', 'watermelon'] 

    in_bisect(fruits, 'banana') 
    in_bisect(fruits, 'ewf')   

Answer 1

Stellen Sie sich vor, was passiert, wenn die Listenlänge ist 1. Dann ist die Mitte 0 sein wird, wenn jetzt der letzte else Fall die tatsächliche ist, die Rekursion wird die gleiche Liste (Größe) wieder bekommen, mit dem gleichen Ergebnis ... unendliche Rekursion.

Lösung: Fügen Sie ein bis middle wie in diesem Moment wissen Sie bereits, dass middle selbst nicht mehr ist ein Kandidat:

else: 
    return in_bisect(t[middle+1:], word) 

Answer 2

I Schleife hier statt Rekursion verwenden würde, da Python nicht Endrekursion in Schleife umwandeln und hat eine sehr niedrige Grenze für die Rekursionstiefe.

Ich würde auch überprüfen, ob word in t ist und ansonsten False zurückgeben.

def in_bisect(t, word): 
    def iterator(start, end): 
     # loop will terminate when exactly start = end - 1 
     while start < end - 1: 
      middle = (start + end) // 2 
      if t[middle] == word: 
       return middle 
      elif t[middle] > word: 
       end = middle 
      else: 
       start = middle + 1 
     # here we need to check wheither the last element in the list is the one we search for 
     return start if t[start] == word else False 

    # if len(t) is zero, our inner function would raise IndexError so we check it explicitly 
    if len(t) == 0: 
     return False 
    return iterator(0, len(t))