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

错误就在这里：

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

应该是：

if((last-first)<2):

Answer 2

在整个代码中添加更多 print 调用以了解实际情况会很有帮助。先看搜索结果：

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

你会看到它 returns False up。您已经知道它不是递归的，所以它一定是意外地击中了这个分支：

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

添加一个 print(first - last) 以找出为什么 它会去那里。在您的示例中，它将打印 -14，这肯定小于二。改为测试 last - first，它会给你这个调用链：

最终 return True，正如预期的那样。

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

Unexpected behavior of binary search algorithm in python

python

binary-search