Recursive binary search in Python
Specify Requirements Up Front

The whole point of binary search is that it's O(lg N). If you're going to check that the array is sorted first, you may as well do a linear search. Not to mention that you're doing even worse here since you're checking that the array is sorted on every recursive call, so now we have an O(N lg N) search. Binary search should assume a sorted list. If the user doesn't provide one, it's garbage in garbage out.

Use appropriate defaults

Usage-wise, it makes more sense to just write:

idx = binSearch(ary, 5)


So let's do:

def binSearch(ary, elem):
    def recurse(first, last):
        ...

    return recurse(0, len(ary)-1)


What if it's not found?

You should have an error case, if first &gt; last, you should return None. Otherwise, you have infinite recursion.

Full solution:

def binSearch(ary, elem):
    def recurse(first, last):
        mid = (first + last) / 2 
        if first &gt; last:
            return None
        elif (ary[mid] &lt; elem):
            return recurse(mid + 1, last)
        elif (ary[mid] &gt; elem):
            return recurse(first, mid - 1)
        else:
            return mid 

    return recurse(0, len(ary)-1)