Find minimum in rotated sorted array The given code find the minimum element in a sorted array rotated by some fixed distance.
Eg: [1, 2, 3, 4, 5, 6, 7] -&gt; [3, 4, 5, 6, 7, 1, 2]

The elements in the array are all unique. Just wanted to check if the code handles all edge cases and is correct.

def findMin(ary):

    def recurse(lo, hi):
        # Base cases   
        if (ary[lo] &lt; ary[hi]):
            return ary[lo]
        if (hi - lo == 1):
            return min(ary)

        mid = lo + (hi - lo) / 2
        if (ary[mid] &lt; ary[hi]):
            return recurse(lo, mid)
        else:
            return recurse(mid, hi)

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


ary = (3, 4, 5, 6, 7, 1, 2)
print findMin(ary) # 1
Why are you giving up?

if (hi - lo == 1):
    return min(ary)


So we're almost done with our nice O(lg N) algorithm, when suddenly... we start over and do a whole new O(N) search from scratch throwing everything away? Why? Let's examine such a scenario:

ary = [3, 4, 5, 6, 0, 1, 2]

lo = 0, hi = 6, mid = 3
ary[mid] (6) &gt; ary[hi] (2), so recurse mid to hi

lo = 3, hi = 6, mid = 4
ary[mid] (0) &lt; ary[hi] (2), so recurse lo to mid

lo = 3, hi = 4
hi - lo == 1, so return min(ary) == 0


At this point, we have ary[lo] == 6 and ary[hi] == 0. We know one of those two is the minimum, and we know which one that is. So let's use that information:

def recurse(lo, hi):
    # Base cases   
    if (ary[lo] &lt; ary[hi]):
        return ary[lo]
    elif (hi - lo == 1):
        return ary[hi] ## just return a number, don't call min()
    else:
        mid = ...
        # rest as before