二进制搜索函数python

Question

下面的第一个函数搜索调用时提供的某个数字。目标是减少搜索机制的大小。每次查找数字时，它只查找两端，并减少查找一半的增加效率。

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 = range(1000000) 
x = search(s, 5000000) 
print x 

它产生结果是这样的：

(0, 999999, 1) 
(500000, 999999, 2) 
(500000, 749998, 3) 
(500000, 624998, 4) 
(500000, 562498, 5) 
(500000, 531248, 6) 
(500000, 515623, 7) 
(500000, 507810, 8) 
(500000, 503904, 9) 
(500000, 501951, 10) 
(500000, 500974, 11) 
(500000, 500486, 12) 
(500000, 500242, 13) 
(500000, 500120, 14) 
(500000, 500059, 15) 
(500000, 500028, 16) 
(500000, 500013, 17) 
(500000, 500005, 18) 
(500000, 500001, 19) 
True 

注意它减少了查找机制。但我卡在这里：

if s[mid] > e: return bsearch(s, e, first, mid - 1, calls + 1) 
    return bsearch(s, e, mid + 1, last, calls + 1) 

无法理解它在这里做什么id。谁能解释请

Answer 1

这是递归的一个经典的例子：一个函数调用本身，而是根据不同的参数（在这种特殊情况下第一和最后）。请注意，该函数假定搜索顺序是有序的：每个后续成员不小于前一个成员。这使得有可能在每次递归调用中将搜索到的空间减半，因为很清楚目标的哪一半可能发生。