# Implementation of binary search

I am new to the divide and conquer paradigm. I wanted to verify that there's nothing wrong with this implementation of binary search.

I ran it a few times and it does print the correct result, but I also wanted a sanity check and any possible improvements.

def search(array, item):

if len(array) == 1:
if array == item:
return 1
return 0

mid = len(array) // 2
x = array[:mid]
y = array[mid:]

found = []

found.append(search(x, item))
found.append(search(y, item))

for elm in found:
if elm ==  1:
return True

return False

print(search([1,2,3,4], 8))
print(search([1,2,3,4], 3))


Also, the running time of this is $O(n log(n))$, correct? $O(log(n))$ being the recursion and $O(n)$ being the loop that checks the result list.

• this ... you do know that the time complexity of a binary search should be just $O(\log(n))$? – Vogel612 Mar 25 '17 at 18:39

It looks almost correct. But it can be improved.

### Bug

What will happen if the input array is empty? Stack overflow.

### Boolean values

Why return 1 for true and 0 for false instead of using boolean values?

if array == item:
return 1
return 0


In fact you could return the result of the boolean expression directly:

return array == item


Similarly, what's happening here?

found = []

found.append(search(x, item))
found.append(search(y, item))

for elm in found:
if elm ==  1:
return True

return False


You append 0-1 values into found. If found contains a 1, return True, otherwise return False. All this could be written on a single line:

return search(left, item) or search(right, item)


I also renamed the meaningless x and y to left and right.

### Use doctests

Doctests are awesome. They are easy to write and execute and can greatly increase your confidence in your code and make it possible to refactor the code safely. For example:

def search(array, item):
"""
>>> search([], 1)
False

>>> search([1,2,3,4], 8)
False

>>> search([1,2,3,4], 0)
False

>>> search([1,2,3,5], 4)
False

>>> search([1,2,3,5], 3)
True

>>> search([1,2,3,5], 5)
True

>>> search([1,2,3,5], 1)
True

"""

if not array:
return False

if len(array) == 1:
return array == item

mid = len(array) // 2
left = array[:mid]
right = array[mid:]

return search(left, item) or search(right, item)


You can run this with python -m doctest script.py. If any of the test cases fails, you'll get a nice report (otherwise no output).