python bisection search exercise

Question

나는 한동안 그것을보고 있었고 나의 이분 탐색에 잘못된 점을 알 수 없다. 내가 실행하면 'RecursionError : 최대 재귀 깊이가 비교 대상을 초과했습니다'라고 표시됩니다. 아무도 볼 수 없었고 아래에서 무엇이 잘못되었는지 보았습니까? 고맙습니다! 목록 길이가 최종 else 경우, 재귀가 같은과, 다시 같은 목록 (크기)를 얻을 것이다 실제 하나입니다 지금 경우 1. 다음 중간이 0이 될 것입니다 때 발생하는 상상

#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

결과 ... 무한 재귀.

해결 방법 : 이미 middle 자체가 더 이상 후보임을 알지 그 순간으로 middle에 하나를 추가 : 파이썬 루프에 꼬리 재귀를 변환 할 수 있기 때문에

이

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

Answer 2

내가 대신 재귀 여기에 루프을 사용하고 재귀 깊이가 매우 낮습니다.

나는 word이 t이고 다른 경우는 False 인 것으로 확인합니다.

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))