Finding the second-largest value in an array 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 &gt; hi):
      lo = mid
      mid = hi
      hi = x
    elif ( x &lt; hi and x &gt; mid):
      lo = mid
      mid = x
    elif ( x &lt; lo):
      lo = x
  return mid

print(getSecondHighest(testCase))
Trust the math. When the x &gt; hi comparison fails, there is no need to test against x &lt; hi. The streamlined code should look like

    if x &gt; hi:
        ....
    elif x &gt; 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++.