Recursive binary search in Python I have implemented a recursive binary search in Python and tried to implement some verification to my code. Other than that, is there any optimization I am missing?

def isSorted(ary):
    for i in range(1, len(ary)):
        if (ary[i] &lt; ary[i - 1]):
            return False
    return True


def binSearch(ary, elem, first, last):
    if not isSorted(ary):
        raise AssertionError("Elements are not in sorted order!")
    mid = (first + last) / 2
    if (ary[mid] &lt; elem):
        return binSearch(ary, elem, mid + 1, last)
    elif (ary[mid] &gt; elem):
        return binSearch(ary, elem, first, mid - 1)
    else:
        return mid

ary = (1, 2, 3, 4, 5, 6, 7)
print binSearch(ary, 5, 0, len(ary) -1)
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)