On Binary Search

I was just trying to execute this code snippet for binary search:

def search(L, e):
    def binarySearch(L, e, low, high):
        if (low == high):
            return L[low] == e
        mid = low + int((high-low)/2)
        if L[mid] == e:
            return True
        if L[mid] > e:
            return binarySearch(L, e, low, mid - 1)
        else:
            return binarySearch(L, e, mid + 1, high)

    if len(L) == 0:
        return False
    else:
        return binarySearch(L, e, 0, len(L) - 1)

For elements that are in the list, this code works fine, but for the elements that are not in the list, this goes on for a toss. The reason is that depending on the element being left of low or right of high, mid will reach low or high respectively eventually. Once it reaches that point, for the first case, mid – 1 will be -1. And the problem is (-1/2) in python is, for some unknown reason, -1 and not 0. So, mid will also be -1 in the current run and in the next pass mid will be -2. Given that -2/2 is also -1, we are stuck with the same values of low, mid and high from there on.

The fix is to keep this small check when calling the recursive function:

def search(L, e):
    def binarySearch(L, e, low, high):
        print "(%d, %d)" % (low, high)
        if (low == high):
            return L[low] == e
        mid = (low + high)/2
        if L[mid] == e:
            return True
        if L[mid] > e:
            return binarySearch(L, e, low, max(low, mid - 1))
        else:
            return binarySearch(L, e, min(mid + 1, high), high)

    if len(L) == 0:
        return False
    else:
        return binarySearch(L, e, 0, len(L) - 1)

When passing mid, we keep a check.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s