2016-12-22 61 views
1

我是新來的python,所以我不知道我是否缺少明顯的東西(例如冒號或某個地方的某個時期)。二進制搜索使用遞歸進入一個無限循環

我試圖使這個二進制搜索算法的工作,但如果我通過一個大於3個元素的列表程序進入無限遞歸制動和python中設置的最大值。

基準情況下工作正常。

[]和[element1]列表通過。

[部件1,element2的,元素3,...,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) 

感謝。

+0

這或許可以幫助你:https://interactivepython.org/runestone/static/pythonds/SortSearch/TheBinarySearch.html – iFlo

+1

想想,如果你運行會發生什麼'BINSEARCH([1],2)'。 –

+0

對我來說沒什麼明顯的。在大多數情況下,Python解釋器可以診斷類似你提到的那些缺陷(但當然不總是)。建議:掌握一個可以設置斷點的開發環境(IDE),以便您可以檢查程序中變量的內容,或者簡單地放入臨時* print *語句,以便可以推斷出推理的位置已經消失錯誤。 –

回答

1

我們顯然必須假設數據是排序的,否則二分查找是毫無意義的。首先,你失蹤時的元素等於樞軸本身的情況:

if element == pylist[mid]: 

而且,在此塊:

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

你不處理,你必須離開一個元素的情況下和它的不是你想要的元素,在這種情況下你應該返回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) 

當然是有空間來使此代碼更有效,但是這僅僅是修正代碼,它被賦予。

0

好的。必須做一個冒泡排序函數來排序一個沒有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)