# 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. Sep 4 '15 at 20:27
• I believe this approach doesn't work if there are repeated entries in the array. Sep 4 '15 at 21:30
• I belive you wanted to return ary[hi] if (hi - lo == 1), right? 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. Sep 5 '15 at 2:26
• @Jaime, yes already written in the problem description above. 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, 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. 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! Sep 7 '15 at 9:18
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.28525638580322266, "perplexity": 2560.1316371298153}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2021-39/segments/1631780057973.90/warc/CC-MAIN-20210926205414-20210926235414-00573.warc.gz"}