二進制搜索函數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

這是遞歸的一個經典的例子：一個函數調用本身，而是根據不同的參數（在這種特殊情況下第一和最後）。請注意，該函數假定搜索順序是有序的：每個後續成員不小於前一個成員。這使得有可能在每次遞歸調用中將搜索到的空間減半，因爲很清楚目標的哪一半可能發生。