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

1 Answer 1

Reset to default
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
\$\endgroup\$
3
  • \$\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
    Commented Sep 5, 2015 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
    Commented Sep 5, 2015 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
    Commented Sep 7, 2015 at 9:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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