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

Mike Bessonov · Accepted Answer · 2015-04-02 20:47:34Z

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.

answered Apr 2, 2015 at 20:47

Mike Bessonov

6863 silver badges8 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

facebook-1422110434758753 Over a year ago

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 Over a year ago

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.

Collectives™ on Stack Overflow

Binary search function python

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related