AbdulFattah Popoola - 7 months ago 81

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

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.

Source (Stackoverflow)