4
\$\begingroup\$

The problem is stated as:

You are given as input an unsorted array of n distinct numbers, where n is a power of 2. Give an algorithm that identifies the second-largest number in the array and that uses at most n+log(n)−2 comparisons.

I've seen many references to the problem online but most focus on a recursive approach. I wonder why that is. Below is how I approached it. Is there an issue with this implementation? Why choose recurrence here?

testCase = [10, 9, 5, 4, 11, 100, 120, 110]
def getSecondHighest(a):
  hi = mid = lo = 0
  for i in range(0, len(a)):
    x = a[i]
    if ( x > hi):
      lo = mid
      mid = hi
      hi = x
    elif ( x < hi and x > mid):
      lo = mid
      mid = x
    elif ( x < lo):
      lo = x
  return mid

print(getSecondHighest(testCase))
\$\endgroup\$
9
  • \$\begingroup\$ your test case only has 8 numbers. should it not have either 4,9 or 16? \$\endgroup\$
    – BenKoshy
    Jun 2, 2017 at 5:48
  • \$\begingroup\$ Your code is broken since it uses too many comparisons. In your code, count the actual comparisons and assert that there aren't too many. Use more than one test case. Especially rising numbers and falling numbers make interesting test cases. \$\endgroup\$ Jun 2, 2017 at 6:09
  • \$\begingroup\$ @RolandIllig I used a bunch of test cases and couldn't find a failing one. What do you mean by "too many comparisons" \$\endgroup\$
    – silkAdmin
    Jun 2, 2017 at 6:26
  • 1
    \$\begingroup\$ @RolandIllig Code is "broken" when it doesn't work as intended. Code that's ugly/inefficient/doesn't follow coding conventions may still work as intended and as such not "broken". \$\endgroup\$
    – ChatterOne
    Jun 2, 2017 at 6:43
  • 1
    \$\begingroup\$ @silkAdmin It was just an example. I don't think the code is inefficient. I do think it's ugly though :-P Variable names are meaningless and the function name uses camel case instead of snake case, for example. You can look at PEP8 to get an idea. \$\endgroup\$
    – ChatterOne
    Jun 2, 2017 at 6:48

2 Answers 2

7
\$\begingroup\$
  • Trust the math. When the x > hi comparison fails, there is no need to test against x < hi. The streamlined code should look like

        if x > hi:
            ....
        elif x > mid:
            ....
        else
            ....
    
  • Follow the math. In the worst case - the array sorted in the descending order - (almost) every element has go through two comparisons, making total of \$2n - 2\$, which is larger than the goal of \$n + \log{n} - 2\$

  • A correct approach is to arrange an elimination tournament (\$n - 1\$ comparisons to determine a champion), while keeping track of those who lose only to the champion. This makes \$log{n}\$ candidates for the second place, and \$\log{n} - 1\$ comparisons to determine the second. For the details, watch Alex Stepanov lectures starting with lecture 8, or just see the final code.

    I highly recommend to watch the entire course, even if you are not interested in C++.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Well, you could kind of "cheat" a bit and use a count sort to get \$O(n-2)\$ comparisons (Because you still need to find the two integers that you need) :-P But of course you'd need some constraint on the max value. \$\endgroup\$
    – ChatterOne
    Jun 2, 2017 at 9:57
  • \$\begingroup\$ @ChatterOne Using a count sort would be useless, "unsorted array of n distinct numbers". \$\endgroup\$
    – Peilonrayz
    Jun 2, 2017 at 10:28
  • \$\begingroup\$ @Peilonrayz Huh? Yes, the fact that they are unsorted is exactly why a count sort would be useful. \$\endgroup\$
    – ChatterOne
    Jun 2, 2017 at 10:58
  • 1
    \$\begingroup\$ @ChatterOne They're "distinct numbers", your count sort will produce the same list, but with each having a 'count' of 1. \$\endgroup\$
    – Peilonrayz
    Jun 2, 2017 at 11:00
  • 1
    \$\begingroup\$ @Peilonrayz Yes, but that doesn't matter. What matters is that the list will already be sorted and all you need to do is find the top two which are actually present, hence the \$O(n-2)\$ comparisons \$\endgroup\$
    – ChatterOne
    Jun 2, 2017 at 11:15
2
\$\begingroup\$

I have about 3 hours experience of Python under my belt so I didn't even know snake case was favored :).

Fortunately Python follows the style guide PEP8, and so if you read that you'll be up-to-date on all, most, of Pythons conventions.

However it mostly comes down to using snake_case, removing some unneeded parentheses, and keeping to Python's somewhat strict whitespace rulings.


As for your code, you don't need lo, and since you have at most 4 / 5 comparisons per loop your code probably doesn't fit in the limit of \$n + \log(n) − 2\$. You should also use for x in a, rather than getting i to then index a. And so after a little cleanup you can get:

def get_second_highest(a):
    hi = mid = 0
    for x in a:
        if x > hi:
            mid = hi
            hi = x
        elif x < hi and x > mid:
            lo = mid
            mid = x
    return mid

print(get_second_highest([10, 9, 5, 4, 11, 100, 120, 110]))

This really depends on what you count as a comparison. For example does for i in range(10) count as zero, one or ten comparisons. If you were to write the same thing in any other language it'd definitely be ten, for (var i = 0; i < 10; i++). And so if you count using loops as 0, then it's really quite simple. You can do it in less than n comparisons.

To do this go through half the array, and move the higher ones to the front of the array. Keep doing this for the bit length of the size of the list.

def get_second_heighest(a):
    mid = len(a)
    for _ in range(mid.bit_length()):
        mid, add = divmod(mid, 2)
        add += mid
        for i in range(mid):
            if a[i] < a[i + add]:
                a[i], a[i + add] = a[i + add], a[i]
    if len(a) >= 2:
        return a[1]
    return None
\$\endgroup\$
3
  • \$\begingroup\$ Thanks @Peilonrayz ! However, I am really confused by the second part of your answer. Why using bit_length length? I don't see how it correlates to the actual length of the array. mid, add = divmod(mid, 2) what is this for ? \$\endgroup\$
    – silkAdmin
    Jun 3, 2017 at 11:28
  • 1
    \$\begingroup\$ @silkAdmin Think of the numbers in binary form. Take bin(10) which is 0b1010, so the bit length of that is 4. Then look at divmod, where we reassign mid as mid //= 2. So taking 10 again, since we loop 4 times, we have the following numbers: (bin(10), bin(10 // 2), bin(10 // 2 // 2), bin(10 // 2 // 2 // 2)), which are, 1010, 101, 10, 1. And so we're halving the number until it reaches zero. However rather than using while mid, instead of the current for loop, I instead used some binary logic to reduce the amount of comparisons. \$\endgroup\$
    – Peilonrayz
    Jun 3, 2017 at 14:39
  • \$\begingroup\$ Thanks for clarifying @Peilonrayz, It's a pretty impressive thinking there. I need to take the time to understand this. \$\endgroup\$
    – silkAdmin
    Jun 5, 2017 at 1:53

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.