算法：找第2个最小元素的索引从一个名不见经传的数组 [英] Algorithm: Find index of 2nd smallest element from an unknown array
问题描述
我一直在思考关于我一会儿功课的问题。我欢迎（和preFER）如何攻击这个问题的任何建议或办法。
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.
基本上，我有大小N的数组中的我们不知道的元素，但我们知道他们是截然不同的。我有唯一是谁的人会采取两种指数（I，J）的N.那么这个人会告诉我一个[J]是否为＆lt;或> A [1]。我想找到的算法，通过询问和LT找到第二个最小元素的索引; = N +日志ñ问题，这个人
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.
推荐答案
这答案介绍了如何找到第二个最大元素;发现第二小的可以类似地完成。为了简单起见，我们还假定所有的数字是不同的。
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.
为了寻找最大的元素，让我们建立一个'冠军'树：配对的元素，决定哪些是更大（即一个是赢家），然后配对获奖者，决定哪个更大，依此类推，直到你找到'冠军'，这是最大的元素。这需要n步。现在，第二个最大的元素一定是比冠军。 （因为只有冠军能打败它）。登录n个元素进行了比较的冠军，所以从这些，挑选最伟大的;这需要日志n步。
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.
作为一个例子，让我们来看看它是如何工作的数元组[6,4,3,5,2,1]。在第一轮中，对是（6,4），（3,5），（2,1）。获胜者是在每对，即，6,5,2越大的元素。在第二轮对是（6,5），2（2没有对这里，所以它会被自动提升为下一轮）。第二轮获奖者是6和2，在第三轮中唯一对是（6,2），6是赢家。现在，通过配对的元素，并选择一个赢家，我们已经建立了一个（根，二进制）树：
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:
这棵树的财产，对于一个节点 X 及其子 Y，Z 我们是W 没能顶端，所以它在树中的父。但其父是大于或等于是W ，所以在树的一些水平，最大元素的孩子中的一个是是W 。 （换句话说，第二个最大的元件只能'败'通过的最大元素）。所以，我们所要做的就是回去的最大元素已经采取的道路上，并收集所有直接子，我们知道第二大是其中之一。在我们的例子中，这些元素2,5,4。 （一般情况下，大约有日志N 其中，其中登陆表示2为底，因为树是关于日志N 高）。从这些因素我们选择了最大的与采用为log N 步骤的任何方法，而我们发现的第二大。
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'.
这篇关于算法：找第2个最小元素的索引从一个名不见经传的数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
