banchan86
5/23/2017 - 1:52 PM

## Binary_Search_V2 this is slightly more complicated as it will also return the index of the item. Also has recursive and iterative variants

Binary_Search_V2 this is slightly more complicated as it will also return the index of the item. Also has recursive and iterative variants

``````def binary_search(a, x):
mid = (len(a)-1)//2
if len(a) == 0:
return -1
# To catch the edge case where binary_search returns an empty list]
elif x == a[mid]:
return mid
elif len(a) == 1:
return -1
# To catch the edge case where binary_search returns one value but it does not match
elif x < a[mid]:
return binary_search(a[:mid], x)
elif x > a[mid]:
right_value = binary_search(a[mid+1:], x)
if right_value == -1:
# the if portion pass -1 up the recursion stack.
return -1
else:
return mid + 1 + right_value

def binary_search(a, x):
left, right = 0, len(a)-1
while left <= right:
mid = left+(right-left)//2
if x == a[mid]:
return mid
if x < a[mid]:
right = mid - 1
if x > a[mid]:
left = mid + 1
return -1