5
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Some explanation of the problem and what you'd like to get from the reviews would be nice. \$\endgroup\$ – glampert Sep 4 '15 at 20:27
  • \$\begingroup\$ I believe this approach doesn't work if there are repeated entries in the array. \$\endgroup\$ – Jaime Sep 4 '15 at 21:30
  • \$\begingroup\$ I belive you wanted to return ary[hi] if (hi - lo == 1), right? \$\endgroup\$ – Bartek Kobyłecki Sep 4 '15 at 21:52
  • \$\begingroup\$ @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. \$\endgroup\$ – CodeYogi Sep 5 '15 at 2:26
  • \$\begingroup\$ @Jaime, yes already written in the problem description above. \$\endgroup\$ – CodeYogi Sep 5 '15 at 2:27
6
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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, \$\endgroup\$ – CodeYogi Sep 5 '15 at 2:48
  • \$\begingroup\$ @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. \$\endgroup\$ – Bartek Kobyłecki Sep 5 '15 at 6:02
  • \$\begingroup\$ @Barry, ah it makes me feels so idiot. Maybe I need to practice a lot and continue to ask stuffs here. Thanks! \$\endgroup\$ – CodeYogi Sep 7 '15 at 9:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.