2

我对以下 MIT OCW 讲座中提出的 Python 二进制搜索算法有疑问：

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/video-lectures/lecture-9/

这是代码（如果您点击链接，它位于“相关资源”下）：

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

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

其中 s 是整数列表，e 是您正在测试成员资格的元素。

#if s=range(100) and e=-1:

    search(s,e)

返回：

0 99 1
0 48 2
0 23 3
0 10 4
0 4 5
0 1 6
False

在上面的 bsearch 函数中没有定义为返回值的情况下，如何返回 'False'？如果我创建一个在元素位于列表中时返回“True”的函数：

def f(s,e):
's is a list of ints. return 'True' if e  is an element of s'
    if e in s:
        return True

并使用上面相同的 s (range(100)) 和 e (-1)，

>>> f(s,-1)
>>>

False 不会自动返回。

我想知道如果元素不在列表中，bsearch 算法的哪一部分意味着返回值“False”。任何帮助将不胜感激。谢谢！

4

1 回答 1

0

False可能在此行中返回：

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

（即当s[first] != e和s[last] != e）

于 2013-07-15T14:04:17.930 回答