2
votes

I have a question regarding the Python binary search algorithm as presented in the following MIT OCW lecture:

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

Here is the code (if you follow the link, it's found under 'Related Resources'):

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) 

where s is a list of ints and e is the element you are testing for membership.

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

    search(s,e)

returns:

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

How is 'False' returned without being defined as a return value in the bsearch function above? If I create a function that returns 'True' if an element is in a list:

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

and use the same s (range(100)) and e (-1) above,

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

False is not automatically returned.

I'm wondering what part of the bsearch algorithm implies a return value of 'False' if the element is not in the list. Any help would be greatly appreciated. Thanks!

1

1 Answers

0
votes

False is potentially returned in this line:

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

(Namely when s[first] != e and s[last] != e)