python中二进制搜索算法的意外行为

Question

我对Python还不熟悉。在尝试做一个二进制搜索函数时，我遇到了一个意想不到的问题。我不明白为什么会这样。我试图修改代码，但每次的结果都是一样的。代码如下：

def bsearch(s,e,first,last,calls):
    print(first,last,calls)
    if((first-last)<2):
        return (s[first]==e or s[last]==e)
    mid = first + int((last-first)/2)
    if (s[mid]==e):
        return True
    if (s[mid]>e):
        return bsearch(s,e,first,mid-1,calls+1)
    else:
        return bsearch(s,e,mid+1,last,calls+1)

def search(s,e):
    bsearch(s,e,0,len(s)-1,1)

这是我在shell中键入并作为输出获取的内容：

>>> s=[1,2,3,4,5,6,7,8,9,10,11,12,13,15,16]
>>> search(s,5)

输出：

0 14 1

就这样。它不会搜索列表中的元素。你知道吗

Answer 1

在整个代码中添加更多的print调用以了解实际发生的情况可能会有所帮助。首先查看搜索结果：

def search(s,e):
    print(bsearch(s,e,0,len(s)-1,1))

你会看到它直接返回False。您已经知道它不是递归的，所以它一定意外地命中了此分支：

if((first-last)<2):
    return (s[first]==e or s[last]==e)

添加一个print(first - last)来找出它为什么会去那里。在您的示例中，它将打印-14，这肯定小于2。改为testlast - first，它将为您提供以下调用链：

0 14 1
0 6 2
4 6 3
4 4 4

最终返回True，正如预期的那样。你知道吗

Answer 2

错误就在这里：

if((first-last)<2): #This always will be less than 2

应该是：

if((last-first)<2):