我的递归二进制搜索我在哪里出错

Question

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个数组，但没有找到最后一个。

Answer 1

您可以做：

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 )