Python бинарный поиск функция от OCW

Question

У меня есть вопрос относительно Python бинарного алгоритма поиска, как представлено в следующей MIT ОКУ лекции:

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 

Как можно 'False' возвращается без определяется в качестве возвращаемого значения в функции bsearch выше? Если я создаю функцию, которая возвращает '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 

и использовать одни и те же с (диапазон (100)) и е (-1) выше,

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

False не возвращается автоматически.

Мне интересно, какая часть алгоритма bsearch подразумевает возвращаемое значение «False», если элемент отсутствует в списке. Любая помощь будет принята с благодарностью. Благодаря!

Answer 1

False потенциально возвращается в этой строке:

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

(а именно, когда s[first] != e и s[last] != e)