Algorithm: find the index of the second smallest element from an unknown array

Question

I thought about my homework for a while. I welcome (and prefer) any suggestions or approach to solving this problem.

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

Answer 1

This answer describes how to find the second greatest element; the search for the second smallest can be done in a similar way. For simplicity, we also assume that all numbers are distinct.

To find the greatest element, let's build a championship tree: connect the elements, decide which is greater (the one who is the winner), then combine the winners, decide which is greater, and so on, until you find the “champion” who is the biggest an element. It takes n steps. Now the second greatest element must be compared with the champion. (because only the champion could defeat him). log n elements were compared with the champion, so choose the largest of them; it takes log n steps.

As an example, let's see how this works for a set of numbers [6,4,3,5,2,1]. In the first round of the pair (6.4), (3.5), (2.1). Winners are big elements in each pair, i.e. 6.5.2. In the second round of the pair (6.5), 2. (2 does not have a pair here, so it automatically rises to the next round). The winners of the second round are 6 and 2, in the third round there is a single pair (6.2), 6 is the winner. Now, combining the elements and choosing the winner, we created a tree with a root, binary:

This tree has the property that for node x and its children y,z we have x>=y, x>=z , so we know that the largest element belongs to the vertex (in the root). We also know that the second greatest element of w did not hit the vertex, so it has a parent element in the tree. But its parent element is greater than or equal to w , therefore, at some level of the tree, one of the children of the largest element w . (In other words, the second greatest element can be “defeated” by the largest element). So, all we need to do is return to the path that the greatest element has taken, and collect all the direct children, we know that among them there is the second largest. In our case, these are elements 2,5,4. (In general, of these, about log n , where log denotes the logarithm of the base two, because the tree has a value of log n high.). Of these elements, we select the largest with any method that takes log n steps, and we find the second largest.

All this may remind us of the championship, where the numbers indicate how “good” each team is, therefore, the term “championship tree”.

Answer 2

First find the smallest item. You can do this with n-1 comaparisons so that each element compares with most log (n) of the other elements. Now look at which elements were mapped to the smallest element and find the smallest of them.

Answer 3

 unknown array = a[]. min1 = a[0]. first element. min2 = 0. can equal anything for(start at 0, until the end, grow by one): if(min1 > a[n]): min2 = min1. min1 = a[n]. return min2. 

Answer 4

Attacking such problems is often best done with divide and conquer. That is, try to simplify / separate the problem, solve the simpler problem (s), and then see if it gives any understanding that will help you solve the original question. If a simpler problem is still too complicated, try simplifying it, etc.

In this case, you can start by looking for the smallest element from the array. How do you do this?

Answer 5

Look at sorting algorithms, such as merge sorting, which has worse O (n log n) complexity. A “man” telling you that A [j]> A [i] is true or false is obviously a comparison function.

Sorting sort recursively divides your array into two smaller arrays by half the size of the original array, and then again applies the merge sort algorithm to these arrays. If you come to the final step of two arrays with only one element, you will ask the person / comparison function to tell you how to sort these arrays / elements. From this step, you will begin to combine your subarrays with the original, but now sorted, array.

In the end, you can simply return the second element of the sorted array, this will be the second smallest.

Answer 6

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

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

Answer 7

Legends

S Cosmic Complexity T Complexity of Time

I'm Arnab Dutta. I say ... why not go:

 1. maintain the elements as a MIN-HEAP array [S = 0, T = O(n) if optimized <- ignore as its 1 time activity] 2. call deleteMin() 2 times [T <= h(tree_height) - as internally deleteMin() calls shiftDown()] 

Thus, the sum T = O (h)

Anyone who has an explanation of why this is not better if used

  a. Tournament or b. using MAX-HEAP 

Note. Step 1 can be said about the complexity of space and time.