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.

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).