Recursive binary search implementation in Python 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] &lt; 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] &gt; 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()
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.