Recursive binary search implementation in Python
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.