파이썬에서 재귀 바이너리 검색

Question

나는 거의 쓸모없이이 기능을 이해하려고 노력하고있다. 바이너리 검색이 무엇인지 완전히 이해하지만 재귀라는 개념은 처음이지만 약간의 이해가 있습니다. 처음에는 함수를 호출 할 때 low와 high의 기본값이 무엇인지 이해하지 못합니다. 현재로서는 번호가 들어있는 검색 공간을 포함하는 것입니다. 그러나 목록 길이를 모르는 경우 또는 목록 길이가 확실하지 않은 경우 어떻게해야합니까? 그렇지 않으면, 나는 여기에서 진행되는 재귀 과정과 낮고 높은 논증에 대한 필요성을 이해합니다. 아래의 기능은 필자가 복용하고있는 온라인 코스의 노트에 제공됩니다. 그러나, 그것은 강의에서 설명되지 않았으며 그것에 관한 문서화 또는 참조를 포함하지 않습니다.

def bSearch(L, e, low, high): 
    if high - low < 2: 
     return L[low] == e or L[high] == e 
    mid = low + int((high-low)/2) 
    if L[mid] == e: 
     return True 
    if L[mid] > e: 
     return bSearch(L, e, low, mid-1) 
    else: 
     return bSearch(L, e, mid+1, high) 

L = [1,3,6,15,34,84,78,256] 
print bSearch(L, 15, 4, 8) 
print bSearch(L, 84, 0, 6) 

출력 :

False 
True 

Answer 1

높고 낮은 검색하는 목록의 부분에 대한 인덱스가 나타납니다. 첫 번째 예

, 15는 3의 인덱스를 가지고 있으므로 4 낮은 인덱스를 지정하면 15 상기 검색 공간에 포함되지 않는 것을 의미한다. 두 번째 예에서 84은 5의 인덱스를 가지므로 인덱스 0 및 6에 해당하는 검색 공간에 포함됩니다.

이 지수는 포괄적입니다. 두 번째 예제가 있다면 :

는

print bSearch(L, 84, 0, 5) 

대답은 다음과 같습니다

True 

는 전체 목록을 검색하려면, 당신은 간단하게 수행 할 수 있습니다

print bSearch(L, 84, 0, len(L) - 1) 

을 - 1이고 검색 기능이 포괄적이기 때문에 필요합니다.

Answer 2

이진 검색.

bsearch (목록, 찾을 요소, 시작 색인, 종료 색인). 시작 인덱스 함수 마지막 인덱스의 시작에서 0으로 간주 될 수 LEN (목록)로 간주 될 수 -1

로서 질문에 대한 bsearch (L, 15, 4, 8). U는 번호가없는 5 번째와 9 번째 요소 사이에서만 검색 중입니다.

두 번째 함수 호출에서 u는 첫 번째 요소와 다섯 번째 요소 (숫자가있는 위치) 사이를 검색합니다.

U는 다른 모든 숫자에 대해 bsearch (L, 15, 0, len (L) - 1)로 부를 수 있습니다.

희망이 도움이됩니다.

Answer 3

low 및 high은 알고리즘이 검색해야하는 L의 색인을 지정합니다. 첫 번째 예에서 15는 인덱스 3을가집니다. 이것은 [4,8] 간격이 아니므로 false을 반환합니다. 두 번째 예에서 L에있는 84의 색인은 5이며, 이것은 [0,6] 간격에 있으므로 True을 반환합니다.

검색하려는 번호가 L이 아닌 경우이 메서드는 False을 반환합니다. 왜? 결국 기본 케이스가 if (high-low) < 2 이니까요. 이 경우 L[high] or L[low]과 검색중인 번호가 같은지 확인합니다. 두 경우 모두 맞지 않으면 False을 반환합니다. 이는 논리적 인 or의 정의입니다. 이 목록의 길이에 대해 확실하지 않은 경우 귀하가 제공하는 high 또는 low 값이 L의 범위에없는 경우

False or False = False False or True = True True or False = True True or True = True

,이 오류가 발생합니다. 추가 조건을 추가하여 이런 일이 발생하지 않도록 할 수는 있지만 그 내용은 해당 수업의 범위를 벗어난 것 같습니다. :)