3
\$\begingroup\$

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.

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

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.