Binary search algorithm in python

Question

I am trying to implement the binary search in python and have written it as follows. However, I can't make it stop whenever needle_element is larger than the largest element in the array.

Can you help? Thanks.

def binary_search(array, needle_element): 

mid = (len(array)) / 2 

if not len(array): 

raise "Error" 

if needle_element == array[mid]: 

return mid 

elif needle_element > array[mid]: 

return mid + binary_search(array[mid:],needle_element) 

elif needle_element < array[mid]: 

return binary_search(array[:mid],needle_element) 

else: 

raise "Error"

Answer 1

In the case that needle_element > array[mid], you currently pass array[mid:] to the recursive call. But you know that array[mid] is too small, so you can pass array[mid+1:] instead (and adjust the returned index accordingly).

If the needle is larger than all the elements in the array, doing it this way will eventually give you an empty array, and an error will be raised as expected.

To know more about this you can have a look at the following video tutorial:-