재귀를 사용하는 바이너리 검색은 무한 루프에 들어갑니다.

Question

저는 파이썬에 익숙하지 않아서 뭔가 예를 들어 콜론이나 마침표 같은 어딘가에 놓치고 있는지 잘 모릅니다.

이 바이너리 검색 알고리즘을 작동 시키려고합니다. 그러나 3 개 이상의 요소를 전달하면 프로그램은 무한 반복되는 제동과 파이썬의 최대 집합으로 이동합니다.

기본 사례가 정상적으로 작동합니다.

[] 및 [element1] 목록이 통과합니다.

[에서 element1, element2에, element3, ..., element99]

다음은 코드의 ... 박히 :

def binsearch(pylist, element): 
    if len(pylist) == 0: 
     return False 
    elif len(pylist) == 1 and pylist[0] == element: 
     return True 
    else: 
     mid = len(pylist)/2 - 1 
     if element > pylist[mid]: 
      binsearch(pylist[mid:], element) 
     else: 
      binsearch(pylist[:mid], element) 

감사합니다.

Answer 1

분명히 데이터가 정렬되었다고 가정해야합니다. 그렇지 않으면 이진 검색은 무의미합니다.

elif len(pylist) == 1 and pylist[0] == element: 
    return True 

당신은 하나 개의 요소가 남아있는 경우를 처리하지 않습니다

하고이 블록에, 또한

if element == pylist[mid]: 

: 첫째, 당신은 요소가 피벗 자체가 같을 때의 경우 누락 된 그것은 이 아니며 원하는 요소입니다.이 경우 False를 반환해야합니다.

다음은 완전히 수정 코드 :이 코드는보다 효율적으로 객실은 확실히있다

def binsearch(pylist, element): 
    pylist = sorted(pylist) # Just to be sure 
    if len(pylist) == 0: 
     return False  

    if len(pylist) == 1: 
     if pylist[0] == element: 
      return True 
     else: 
      return False 
    else: 
     mid = len(pylist) // 2 
     if element == pylist[mid]: 
      return True 
     elif element > pylist[mid]: 
      return binsearch(pylist[mid:], element) 
     else: 
      return binsearch(pylist[:mid], element) 

이지만,이 주어진대로 이것은 단지 코드를 수정한다.

Answer 2

확인을 완료했습니다. 버블 정렬 함수를 만들어서 set() 함수없이 임의의리스트를 정렬해야했습니다.

def binsearch(pylist, element): 
    if len(pylist) == 0: 
     return False 
    else: 
     v_mid = len(pylist) // 2 
     if pylist[v_mid] == element: 
      return True 
     else: 
      if element > pylist[v_mid]: 
       return binsearch(pylist[v_mid + 1:], element) 
      else: 
       return binsearch(pylist[:v_mid], element)