Recursive binary search implementation in Python

Question

I have this (recursive) binary search implementation in Python, and I want you to criticize every aspect of it. It is a naive implementation, (drilling the basics and stuff), but, I want you to comment on the perceived clarity, maintainability of the code, defensive programming practices, test cases that could be useful but are missing, implicit assumptions that may not hold, pythonic-ness of the code, anything that could help me improve the code.

import unittest

def binary_search(collection, key):
    """ Search for a given key in the list of elements
    passed as a parameter.

    :param collection: The iterable to be searched.
    :param key: The search key.

    Returns the index where the key was found, else the symbolic string 'Not found'.
    """
    # First, make sure that the collection we have been given is truly
    # iterable
    try:
        iterator = iter(collection)
    except TypeError:
        raise TypeError("`collection` is not an iterable collection.")

    # if the collection is empty, it means that we have gone
    # past the boundaries and haven't found a value, so we can
    # safely assume there doesn't exist one in the original collection
    if not collection:
        return "Not found"

    collection_length = len(collection)
    mid = collection_length // 2

    # if we found it great, return the index
    if collection[mid] == key:
        return mid
    # now, if we haven't found it,
    elif collection[mid] < key:
        # if there was only 1 element in the collection before
        # the last call to binary search, this means that the
        # floor division above will have returned a mid == 0,
        # causing the recursive function below to bug out and
        # blow the stack. This is a sentinel to make sure this doesn't
        # happen
        if mid == 0:
            return "Not found"
        res = binary_search(collection[mid:], key)
        return mid + res if res != "Not found" else "Not found"
    elif collection[mid] > key:
        return binary_search(collection[:mid], key)


class BinarySearchTests(unittest.TestCase):
    def test_value_found(self):
        collection = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
        res = binary_search(collection, 3)
        self.assertEqual(res, 2, 'Binary search failed to return expected index of search key.')
        res = binary_search(collection, 5)
        self.assertEqual(res, 4, 'Binary search failed to return expected index of search key.')
        res = binary_search(collection, 11)
        self.assertEqual(res, 10, 'Binary search failed to return expected index of search key.')

    def test_value_not_found(self):
        collection = [1, 2, 3, 4, 5]
        res = binary_search(collection, -1)
        self.assertEqual(res, 'Not found', 'Binary search failed to return expected "Not found" value.')
        res = binary_search(collection, 6)
        self.assertEqual(res, 'Not found', 'Binary search failed to return expected "Not found" value.')

    def test_elements_is_not_iterable(self):
        import socket
        elements = socket.socket()
        key = 1
        self.assertRaises(TypeError, binary_search, (key, elements))
        elements.close()  # so that the interpreter doesn't give us a resource warning.

if __name__ == '__main__':
    unittest.main()

Answer 1

You have some excessive commenting here, it practically doubles the length of your function. Take this for example:

# First, make sure that the collection we have been given is truly
# iterable

It's quite superfluous when your code is clean and simple with a very explicit error message:

try:
    iterator = iter(collection)
except TypeError:
    raise TypeError("`collection` is not an iterable collection.")

Your next comment is helpful:

# if the collection is empty, it means that we have gone
# past the boundaries and haven't found a value, so we can
# safely assume there doesn't exist one in the original collection

But it's so long, why not try make it more concise:

# If the collection is empty, we've gone past the boundaries and haven't
# found a value, it must not exist.
if not collection:
    return "Not found"

Large comments harm readability, because they break apart the bits of the code and make it harder to see what the code is doing. And it's certainly not necessary for code to be conversational.

# now, if we haven't found it,

Instead, treat comments like bullet points. Small concise notes that explain things that aren't self evident from the code itself.

There's no real reason to store collection_length just to get the mid, I prefer in place calculations:

mid = len(collection) // 2

Also since it's a recursive function you end up with this pattern:

    return mid + res if res != "Not found" else "Not found"

You could avoid this by raising a ValueError instead when the value isn't found. Raised errors will exit all levels of the function, and can be handled with a try except if desired. The other advantage is that you're no longer mixing return types. As it stands you either return an int or the string "Not found", which is bad practice. What if the user assumes that they can treat the returned value as a number? Docstring or not, people will make assumptions and you should support them (the reasonable ones that is).

Answer 2

Use an inner function

As you make recursive calls, some conditions are unnecessarily reevaluated, for example checking if the collection is iterable. This is kind of ugly, along with the "sentinel" you put in place for mid == 0.

In a more conventional implementation, you don't slice the input collection, but narrow down the search range, by adjusting start and end boundaries. You could create an inner function with signature:

def _binary_search(start, end):
    # ...

And call it with parameters 0 and len(collection). The function will call itself recursively, replacing the start our end parameters with the recalculated mid. There is no list slicing, no unnecessary conditions, and no odd check on mid == 0. The inner function is not visible outside, it's a hidden implementation detail.

Unit testing

It's generally best to have one assert per test case. It's a bit more work, but it's clearer, and its worth it. The practice also makes you think twice before adding redundant tests that are just noise, and think through more carefully what you're testing and why is it important.

Some interesting cases that would be nice to see cleanly separated:

• should return correct result when match is the first element
• should return correct result when match is the last element
• should return correct result when match is the only element
• should return correct result when match is exactly at mid point
• should return correct result when list is empty

Magic string

The string "Not found" appears multiple times in the implementation. It would be better to put it in a constant and reuse.

Alternative return value for missing

A common practice for the return value of a failed binary search is to return -1 -insertAt where insertAt is the position where the element should be inserted to keep the list sorted.