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):
if needle_element == array[mid]:
elif needle_element > array[mid]:
return mid + binary_search(array[mid:],needle_element)
elif needle_element < array[mid]:
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.
Note: Creating a sub-array each time will result in bad performance for large arrays. It's better to pass in the bounds of the array instead.