Algorithm: Find index of 2nd smallest element from an unknown array

Question

I have been pondering about my homework question for a while. I welcome (and prefer) any suggestions or approach on how to attack this problem.

Basically, I have an array A of size N. We do not know the elements but we know they are distinct. The only thing that I have is a person who will take two indices (i,j) in N. This person will then tell me whether A[j] is < or > A[i]. I want to find the algorithm for finding the index of the 2nd smallest element by asking <= n + log n questions to this person.

Answer 1

Attacking such problems is often best done by "divide and conquer". I.e. try to simplify/divide the problem, solve the simpler problem(s), then see if it gave any insight which helps you solving the original question. If the simpler problem is still too hard, try to simplify it further, etc.

In this case, you could start by finding the smallest element from the array. How would you do that?

Answer 2

Look into sorting algorithms like merge sort, which has a worst case complexity of O(n log n). The "person" telling you if A[j] > A[i] is true or false is obviously a comparison function.

Merge sort works by recursively dividing your array into two smaller arrays half the size of the original array, then applying the merge sort algorithm to these arrays again. If you arrive at a final step of two arrays with only one element, you ask the person/comparison function to tell you how to sort these arrays/elements. From this step up, you begin to merge your sub-arrays back into your orginal, but now sorted array.

At the end, you can simply return the second element of the sorted array, this being the second smallest.

Answer 3

First, find the smallest element. You can do this with n-1 comaparisons in such a way, that each element is compared to at most log(n) other elements. Now look which elements have been compared to the smallest element and find the smallest of those.

Answer 4

1. Use 2 variables - varSmallest and var2ndSmallest
2. Ask person to compare 1st and 2nd value in array - set index of smaller to varSmallest, and the other to var2ndSmallest
3. Take the next index in sequence and name it varIndexToCheck
4. Compare values of varIndexToCheck and of var2ndSmallest - if value of varIndexToCheck is larger than value of var2ndSmallest go to step 3
5. Compare values of varIndexToCheck and of varSmallest - if value of varIndexToCheck is larger than value of varSmallest set var2ndSmallest = varIndexToCheck and go to step 3
6. Else, set var2ndSmallest = varSmallest and varSmallest = varIndexToCheck and then go to step 3

Repeat until there are no more indexes. After that, resulting index is inside var2ndSmallest variable and it is O(n log n) complexity

Answer 5

This answer describes how to find the second greatest element; finding the second smallest can be done analogously. For simplicity, we also assume that all numbers are different.

In order to find the greatest element, let us build a 'championship' tree: pair up the elements, decide which is greater (that one is the 'winner') then pair up the winners, decide which is greater, and so on, until you find the 'champion', which is the greatest element. This takes n steps. Now, the second greatest element must have been compared to the champion. (because only the champion could defeat it). log n elements have been compared to the champion, so from these, pick the greatest; this takes log n steps.

As an example, let us see how this works for the number tuple [6,4,3,5,2,1] . In the first round, pairs are (6,4), (3,5), (2,1). Winners are the greater elements in each pair, that is, 6,5,2. In the second round pairs are (6,5), 2. (2 has no pair here so it will get promoted to the next round automatically). Winners of the second round are 6 and 2, in the third round the only pair is (6,2), 6 is the winner. Now, by pairing up elements and choosing a winner we have built up a (rooted, binary) tree:

This tree has the property that for a node x and its children y,z we have x>=y, x>=z, so we know that the greatest element is the one at the top (at the root). We also know that the second greatest element w did not make it to the top, so it has a parent in the tree. But its parent is greater than or equal to w, so at some level of the tree, one of the children of the greatest element is w. (In other words, the second greatest element could only be 'defeated' by the greatest element). So all we have to do is go back on the path the greatest element has taken and collect all direct children, we know the second largest is among them. In our case, these are the elements 2,5,4 . (In general, there are about log n of them, where log denotes base two logarithm, because the tree is about log n high.). From these elements we pick the largest with any method that takes log n steps, and we found the second largest.

All this may remind us to a championship, where numbers denote how 'good' each team is, hence the term 'championship tree'.