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.

### Like this:

Like Loading...

*Related*