Return to Answer

• 1

• 29.8k
• 1
• 49
• 93

• 29.8k
• 1
• 49
• 93

A solution has been accepted but let's give some additional comment anyway.

It might be worth storing the result of (h + l)/2 : on top of making things potentially more efficient, it does makes things much easier to read/write.

def binary_search(self, array, target):
 def _binary_search(a, l, h, t):
 if l == h:
 return None
 mid = (h + l)/2
 if a[mid] == t:
 return mid
 elif a[mid] > t:
 return _binary_search(a, l, mid, t)
 elif a[mid] < t:
 return _binary_search(a, mid + 1, h, t)
 else:
 return None
 return _binary_search(array, 0, len(array) - 1, target)

Then, it becomes easier to see that the last branch cannot be reached.

def binary_search(self, array, target):
 def _binary_search(a, l, h, t):
 if l == h:
 return None
 mid = (h + l)/2
 if a[mid] == t:
 return mid
 elif a[mid] > t:
 return _binary_search(a, l, mid, t)
 else: 
 assert a[mid] < t
 return _binary_search(a, mid + 1, h, t)
 return _binary_search(array, 0, len(array) - 1, target)

Also, recursion is slow in Python but before falling for premature optimisations, let's check that things are working fine.

1. assert binary_search2([], 1) is None fails : you should be doing if l>=h instead of if l==h.
2. then assert binary_search2([1], 1) == 0 fails, let's replace l >=h by l > h. 3 then assert binary_search2([2], 1) is None fails, let's replace _binary_search(a, l, mid, t) by _binary_search(a, l, mid - 1, t) to ensure the range becomes smaller and smaller.

Now, things seem to be working slighly better :

def binary_search(self, array, target):
 def _binary_search(a, l, h, t):
 if l > h:
 return None
 mid = (h + l)/2
 if a[mid] == t:
 return mid
 elif a[mid] > t:
 return _binary_search(a, l, mid -1 , t)
 else:
 assert a[mid] < t
 return _binary_search(a, mid + 1, h, t)
 return _binary_search(array, 0, len(array) - 1, target)

Now, we can try to remove the recursion :

def binary_search(self, array, target):
 # if target is in the array, it must be in [low, high]
 low, high = 0, len(array) - 1
 while low <= high:
 mid = (high + low)/2
 if array[mid] == target:
 return mid
 elif array[mid] > target:
 high = mid - 1
 else:
 low = mid + 1
 return None

I haven't performed any benchmark but I reckon this function should be faster (and also, more robust).

Something else you could change to make your code better is stop writing classes. There is no need for a class here and by using one, you are just making things harder to understand/reuse for no reason.