Recursive binary search in Python

Question

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] < 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] < elem):
        return binSearch(ary, elem, mid + 1, last)
    elif (ary[mid] > 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)

Answer 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 > 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 > last:
            return None
        elif (ary[mid] < elem):
            return recurse(mid + 1, last)
        elif (ary[mid] > elem):
            return recurse(first, mid - 1)
        else:
            return mid 

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

Answer 2

You are doing what is often called a three-way binary search, as in each iteration you have three possible results: smaller, larger or equal. This may seem advantageous, because if you find the item early, you may be done with as little as one recursive call. The alternative is to never check for equality, and keep dividing the array in half until you are left with a single item. This has the advantage that, in each iteration, you only do one comparison instead of two, but you will always have to do the full \$\log n\$ recursive calls.

On average you will come out ahead if you do the full \$\log n\$ iterations every time. The way I learned to implement this, is to use an index to the first item to search, and an index past the last item to search for:

def binsearch(haystack, needle, lo=0, hi=None):
    if hi is None:
        hi = len(haystack)
    if hi - lo <= 1:
        if haystack[lo] == needle:
            return lo
        else:
            raise ValueError('needle {} not in haystack'.format(needle))
    mid = lo + (hi - lo) // 2
    if haystack[mid] < needle:
        lo = mid + 1
    else:
        hi = mid
    return binsearch(haystack, needle, lo, hi)

If instead of raising an error you return lo without checking if the needle is indeed in the haystack, things start getting interesting:

def binsearch_left(haystack, needle, lo=0, hi=None):
    if hi is None:
        hi = len(haystack)
    if hi - lo <= 1:
        return lo
    mid = lo + (hi - lo) // 2
    if haystack[mid] < needle:
        lo = mid + 1
    else:
        hi = mid
    return binsearch_left(haystack, needle, lo, hi)

This function returns the first position in which you could insert needle, and keep the haystack sorted, which will also be the first occurrence of needle in haystack if there are repeated values. The neat twist is that, by replacing a single < with a <= you get the following:

def binsearch_right(haystack, needle, lo=0, hi=None):
    if hi is None:
        hi = len(haystack)
    if hi - lo <= 1:
        return lo
    mid = lo + (hi - lo) // 2
    if haystack[mid] <= needle:  # Have replaced < with <=
        lo = mid + 1
    else:
        hi = mid
    return binsearch_right(haystack, needle, lo, hi)

This functions returns the last position in which needle could be inserted in haystack and still keep it sorted, which corresponds to one past the last occurrence of needle in haystack if it indeed is there.

Not only is this approach often times faster than the three-way binary search approach, it also gives you much better defined returns if the haystack has repeated entries: either the first or the last, not an undefined one.

It is no surprise that Python's standard library's bisect package implements bisect_left and bisect_right following these ideas.

Note that writing this functions iteratively is extremely simple, and a much, much better option:

def binsearch_left(haystack, needle, lo=0, hi=None):
    if hi is None:
        hi = len(haystack)
    while hi - lo > 1:
        mid = lo + (hi - lo) // 2
        if haystack[mid] < needle:
            lo = mid + 1
        else:
            hi = mid
    return lo

Also, note that I am computing mid as lo + (hi - lo) // 2, not (lo + hi) // 2. This is not relevant in Python, because integers never overflow. But in other languages, the form I have used will never overflow if lo and hi areboth positive values. This is a more or less famous bug, that was shipped with standard libraries for years, until someone figured it out.

Answer 3

Your code is all wrong.

I wrote this timing code:

for exp in range(1, 7):
    ary = list(range(10**exp))
    start = time.time()
    res = binSearch(ary, 5, 0, len(ary) -1)
    print("It took {} for 10**{}. Result = {}".format(
        time.time() - start, exp, res))

The output is:

It took 3.0279159545898438e-05 for 10**1. Result = 5
It took 8.916854858398438e-05 for 10**2. Result = 5
It took 0.002868175506591797 for 10**3. Result = 5
It took 0.023810386657714844 for 10**4. Result = 5
It took 0.2799966335296631 for 10**5. Result = 5
It took 3.80861234664917 for 10**6. Result = 5

If you look at the times needed, they are incrementing linearly with the input size (If the input is 10 times bigger, the time needed is about 10 times bigger). The whole point of a binary search is the logarithmic time complexity. There must be a serious bug in your code.

---

After some analysis, I agree with @Barry, the serious bug is:

if not isSorted(ary):
    raise AssertionError("Elements are not in sorted order!")

It runs in in linear time so the whole time complexity degrades. Removing it gives me the times:

It took 1.1444091796875e-05 for 10**1. Result = 5
It took 1.1920928955078125e-05 for 10**2. Result = 5
It took 1.8835067749023438e-05 for 10**3. Result = 5
It took 1.9788742065429688e-05 for 10**4. Result = 5
It took 3.123283386230469e-05 for 10**5. Result = 5
It took 3.695487976074219e-05 for 10**6. Result = 5

About 6 orders of magnitude faster for big inputs and only getting relatively faster.