Unexpected behavior of binary search algorithm in python

Question

I am new to python. While trying to make a binary search function , i am facing and unexpected problem. I don't understand why this is happening. I tried to modify the code, but result is same every time. Here is the code:

def bsearch(s,e,first,last,calls):
    print(first,last,calls)
    if((first-last)<2):
        return (s[first]==e or s[last]==e)
    mid = first + int((last-first)/2)
    if (s[mid]==e):
        return True
    if (s[mid]>e):
        return bsearch(s,e,first,mid-1,calls+1)
    else:
        return bsearch(s,e,mid+1,last,calls+1)

def search(s,e):
    bsearch(s,e,0,len(s)-1,1)

This is what i type in shell and get as Output:

>>> s=[1,2,3,4,5,6,7,8,9,10,11,12,13,15,16]
>>> search(s,5)

Output:

0 14 1

Thats it. It doesn't search the element in the list.

As a style thing, also note that the conditions on if statements don't need to be in parens - so, you can have if (last - first) < 2:, if s[mid] == e: and if s[mid] > e:. — lvc
– lvc, Commented Jun 13, 2015 at 3:11

Iron Fist · Accepted Answer · 2015-06-13 02:43:10Z

1

The Mistake is right here:

if((first-last)<2): #This always will be less than 2

Should be:

if((last-first)<2):

answered Jun 13, 2015 at 2:43

Iron Fist

11k2 gold badges21 silver badges36 bronze badges

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

Comments

lvc · Accepted Answer · 2015-06-13 02:51:51Z

1

It can be helpful to add more print calls throughout your code to find out what is actually going on. Start by looking at the result of the search:

def search(s,e):
    print(bsearch(s,e,0,len(s)-1,1))

You will see it returns False straight up. You already know it isn't recursing, so it must be hitting this branch unexpectedly:

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

Add a print(first - last) to find out why it would be going there. In your example, it will print -14, which is certainly less than two. Change it to test last - first instead, and it will give you this chain of calls:

and ultimately return True, as expected.

answered Jun 13, 2015 at 2:51

lvc

35.2k10 gold badges76 silver badges100 bronze badges

2 Comments

nitish-d Over a year ago

thanks, that worked well, But can you tell me how do i know whether an element is present in the list or not when i search for an element that is not present in the list, it behaves the same way.

lvc Over a year ago

@nkd2195 by checking the return value of bsearch (what I print out in search, consider returning that value instead) - it is True if the value was found, and False otherwise. If you return it from search, then you would be able to do if search(s, 5):, and the code underneath it will execute if and only if the value was found.

Collectives™ on Stack Overflow

Unexpected behavior of binary search algorithm in python

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related