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

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.

StackExchange Code Review Q#120088, answer score: 3