CODEWITHSUNDEEP
pythonbinary-search
nitish-d
nitish-d

Reputation: 241

Unexpected behavior of binary search algorithm in python

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.

Upvotes: 0

Views: 53

Answers (2)

lvc
lvc

Reputation: 35059

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:

0 14 1
0 6 2
4 6 3
4 4 4

and ultimately return True, as expected.

Upvotes: 1

Iron Fist
Iron Fist

Reputation: 10951

The Mistake is right here:

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

Should be:

if((last-first)<2):

Upvotes: 1

Related Questions