Implementation of binary search

Question

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[0] == 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.

• Vogel612: this ... you do know that the time complexity of a binary search should be just \$O(\log(n))\$?

Answer 1

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[0] == item:
 return 1
return 0

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

return array[0] == 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[0] == 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).