Binary search function python

Question

The first function below searches a certain number provided when called. The goal is to reduce the the size of the search mechanism. Each time it looks up for the number it looks up for two ends only and reduces the look up half increasing efficiency.

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)

when i run this for example like this:

s = range(1000000)
x = search(s, 5000000)
print x

It produces result like this:

(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

Notice how it reduces the look up mechanism. But i am stuck here:

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

Can't understand what exactly it id doing here. Can anyone explain please

Answer 1

This is a classical example of recursion: a function calling itself, but with different arguments (first and last in this particular case). Note that the function assumes that the sequence searched is ordered: each subsequent member is not less than the previous one. This makes it possible to cut the searched space in half with every recursive call, because it is clear in which half the target e can occur.

• facebook-1422110434758753: Thank you. can you explain each step with values here: if s[mid] > e: return bsearch(s, e, first, mid - 1, calls + 1) return bsearch(s, e, mid + 1, last, calls + 1)
• Mike Bessonov: We expect the values in the sequence to be sorted in the non-descending order. When we compare the value from the middle of the sequence with the target, s[mid] > e (with the case of a hit, s[mid] == e checked for before), we can figure out if the target is to the left of the middle (from first to mid-1) or to the right of it (from mid+1 to left). Then we call again bsearch() with the corresponding parameters to search in the left or in the right half of the original range.