파이썬에서 이진 검색을하는 동안 오류가 발생했습니다. 코드에 어떤 문제가 있습니까?

Question

import math 

def BinarySearch(A , val , low , high): 
    if high < low : 
     return -1 #not found 
    mid = low + (high - low) /2 
    if A[mid] > val: 
     return BinarySearch(A,val , low , high) 
    if A[mid] < val : 
     return BinarySearch(A,val,low,high) 
    else: 
     return mid #found 


A = [ 12 , 23 , 2 , 33 , 123 , 4 , 5 , 2 , 54 , 555 , 21 ] 
BinarySearch(A , 0 , 0, 10) 

bisect 모듈을 사용하지 않고 이진 검색을 시도했습니다. 그러나 이와 같은 오류가 발생합니다.

File "doubtrob.py", line 8, in BinarySearch 
    return BinarySearch(A,val , low , high) 
RuntimeError: maximum recursion depth exceeded 

Answer 1

각 반복마다 정확히 동일한 검색 공간을 사용하고 있습니다. 또한, 높은 최저점 인 < 2 번을 멈출 필요가 있습니다. 그렇지 않으면 중간 값이 결국 낮아지고 무한 루프에 걸릴 수 있습니다.

제쳐두고 mid은 더 간단하게 (low + high)/2이 될 수 있습니다.

Answer 2

힌트 :이 반환 BinarySearch는()를 호출에 ... 당신은 동일한 매개 변수를 계속 전화, 그래서 동일한 매개 변수와 함께 호출 계속 다음 호출에 같은 자리에 반복 유지

이것은 숙제 문제입니다. 힌트가 끝납니다.

Answer 3

def BinarySearch(A , val , low , high): 
    if high < low : 
     return -1 #not found                                 
    mid = low + (high - low) /2 
    if A[mid] > val: 
     return BinarySearch(A, val , low , mid-1) 
    if A[mid] < val : 
     return BinarySearch(A, val, mid+1 ,high) 
    else: 
     return mid #found 

재귀에는 종점이 있어야합니다. 항상 동일한 매개 변수를 호출하므로 high<low을 결코 충족시키지 않으므로 결코 terminates을 만족하지 않습니다.