我在哪裏出錯我的遞歸二進制搜索？

def BinarySearch(aList, first, last, target): 

    assert 0 <= first < len(aList); last < len(aList) 

    if len(aList) == 0: 
     return False 
    pos = first + last/2 
    pos = round(pos) 
    if aList[pos] == target: 
     return pos 
    else: 
     if target <= aList[pos]: 
      return BinarySearch(aList[:pos], first, pos, target) 
     else:    
      return BinarySearch(aList[pos +1 :], pos + 1, last, target)

這是一個學校問題，參數是通過另一個函數輸入的。測試函數傳遞一個有6個值的數組，我的代碼找到前3個，但不是最後一個。我在哪裏出錯我的遞歸二進制搜索？

來源

2017-03-14 Tom

想想，如果你切片列表會發生什麼剩餘的元素的索引。 – tzaman

即時消失。我的想法是，因爲數組的長度較小，我將需要在遞歸調用中更改參數。如果這樣我不知道該怎麼辦。 – Tom

'aList [：pos]'是否包含'pos'的值？提示：它的作用非常像'range（）'。 – jszakmeister

你可以這樣做：

def BinarySearch(aList, first, last, target): 

    if first < 0 or last < 0 or first > last or first >= len(aList): 
     return -1 

    if len(aList) == 0: 
     return -1 
    pos = (first + last) // 2 
    if aList[pos] == target: 
     return pos 
    elif aList[pos] > target: 
     return BinarySearch(aList, first, pos - 1, target) 
    else:    
     return BinarySearch(aList, pos + 1, last, target)

來源

2017-03-14 14:12:40

我在哪裏出錯我的遞歸二進制搜索？

回答

相關問題