# 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] -> [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] < ary[hi]):
return ary[lo]
if (hi - lo == 1):
return min(ary)

mid = lo + (hi - lo) / 2
if (ary[mid] < 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

• Some explanation of the problem and what you'd like to get from the reviews would be nice. – glampert Sep 4 '15 at 20:27
• I believe this approach doesn't work if there are repeated entries in the array. – Jaime Sep 4 '15 at 21:30
• I belive you wanted to return ary[hi] if (hi - lo == 1), right? – Bartek Kobyłecki Sep 4 '15 at 21:52
• @BartekKobyłecki, I first solve the problem in notebook (since I don't have white board :)) so after trying couple of cases I found that when there are only two elements left then the minimum is within those two elements. For example in the above problem I was left with [7, 1]. I hope I am right. – CodeYogi Sep 5 '15 at 2:26
• @Jaime, yes already written in the problem description above. – CodeYogi Sep 5 '15 at 2:27

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) > ary[hi] (2), so recurse mid to hi

lo = 3, hi = 6, mid = 4
ary[mid] (0) < 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] < 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

• I thought about this case but wasn't sure that this case [0, 1] will not arise but I was sure that at the end there will be always two elements left. Also, if there are only two elements then what's the issue of calling min on it? thanks, – CodeYogi Sep 5 '15 at 2:48
• @CodeYogi, ary is always the reference of the full array.min(ary) is calculating minimum from full array, not two just elements that left. Insted you could code it like: min([ary[lo], ary[hi]]) but as Barry described you know which of these two elements is smaller. – Bartek Kobyłecki Sep 5 '15 at 6:02
• @Barry, ah it makes me feels so idiot. Maybe I need to practice a lot and continue to ask stuffs here. Thanks! – CodeYogi Sep 7 '15 at 9:18