# Minimum number of comparisons to find $2$nd smallest element

Show that the second smallest of $$n$$ elements can be found with $$n+\lceil\lg n\rceil-2$$ comparisons in the worst case. (Hint: Also find the smallest element.) 

I tried but I have no idea how to, e.g. the best I could do is

//assume n>=2
//A: array of size n
//returns second smallest in A
//0 indexing in C++

int second_smallest(int*A,int n){
queue<int> q;//always keep the size to 2 by push & pop. Also it stores indices.
q.push(1);//2nd smallest
q.push(0);//smallest
for(int i=1;i<n;++i){
if(A[i]<A[q.back()]){
q.push(i);
q.pop();
}
}
int i=q.back()+1;//we know for sure A,...,A[q.back()-1] are greater than A[q.front()]. And A[q.back()] is the smallest.
q.push(q.front());//after this line, assume q.back() is 2nd smallest
q.pop();
for(;i<n;++i){
if(A[i]<A[q.back()]){
q.push(i);
q.pop();
}
}
return A[q.back()];
}


which conducts $$(n-1)+(n-2)=2n-3$$ comparisons in worst case. When input is uniformly distributed over all permutation the average number of comparisons is $$(n-1)+n-E[q.back()]=\frac{3}{2}n-\frac{1}{2}$$ where $$q.back()$$ refers to the one at $$(*)$$, and we know $$E[q.back()]=\frac{1}{n}(1+...+n)=(n-1)/2$$.

But this's no where near $$n+\lceil\lg n\rceil-2$$ so I'm out of idea could someone help?

 Introduction to Algorithms,MIT

Assume that all elements are distinct (if not, replace each element with a pair $$(element, position)$$ and perform the comparisons lexicographically) and consider a rooted binary tree $$T$$ with $$n$$ leaves in which each vertex has either $$0$$ or two children and every level, except possibly the last, is completely filled. Arbitrarily associate each leaf of $$T$$ with a distinct input element.

You can find the minimum by computing, for each interval vertex $$v$$, the minimum among all the elements associated to the leaves of the subtree of $$T$$ rooted at $$v$$. This can be done by performing a postorder visit of $$T$$: whenever $$v$$ is visited, let $$v_\ell$$ and $$v_r$$ be its two children, compare the elements associated with $$v_\ell$$ and $$v_r$$ and let the minimum among the two be the winner; the element associated with $$v$$ is exactly such winner.

At the end of the visit, the root of the tree will be associated with the minimum element of the input sequence.

Consider now the set $$P$$ of the vertices that have been associated with the minimum element and notice that they induce a root-to-leaf path in $$T$$. Let $$C(P)$$ denote the set of all children of the vertices in $$P$$. Since the second-smallest element $$x$$ can only lose against the minimum element, there must be a vertex associated with $$x$$ among those in $$C(P) \setminus P$$ (and this set contains no vertex associated with the minimum element). Then, you find the second-minimum of the input sequence be looking for the minimum of the elements associated with the vertices in $$C(P) \setminus P$$.

The overall number of comparisons is given by the sum of 1) the number of comparisons used to find the minimum, and 2) the number of comparisons needed to handle $$C(P) \setminus P$$. Regarding 1), we perform exactly $$1$$ comparison for each internal vertex, for a total of $$n-1$$ comparisons. Regarding 2), we perform $$|C(P) \setminus P| - 1$$ comparisons, where $$|C(P) \setminus P|$$ is at most the depth of $$T$$, i.e., $$|C(P) \setminus P| \le \lceil \log n \rceil$$. Then: $$(n-1) + (|C(P) \setminus P|-1) \le (n-1) + (\lceil \log n \rceil - 1) = n + \lceil \log n \rceil - 2.$$

The above is this is just a handy description for the analysis of the number of comparison. You don't actually need to build and traverse the tree $$T$$. Here is a possible recursive implementation:

Input: a non-empty list L of distinct elements
Output: the second-minimum in L
Second-Minimum(L):
(x, S) = Find-Candidates(L)
Return the minimum in S

Input: a non-empty list L of distinct elements
Output: a pair (x, S), where x is the minimum in L, and S is a set of candidate second-minimum elements
Find-Candidates(L):
If |L|==1:
return (x, {}), where x is the only element in L

Split L into L' and L'' with | |L'| - |L''| | <= 1
(x', S') = Find-Candidates(L')
(x'', S'') = Find-Candidates(L'')

If x' < x'':
Return (x', S' U {x''})
Else:
Return (x'', S'' U {x'})


Based on Steven's great answer, and some modification so that the second minimum is computed "on the fly" (this won't change the number of comparison) below implemented the algorithms in C++ that also prints the tree for visualization

e.g. with input array L = 3,1,5,2,4 the second smallest is 2 and the tree is printed after $$90$$ degree rotation to the right

                4
2
2
1
5
1
1
1
3


code:

#include <iostream>
#include <stack>
using namespace std;
//declare only
int*Find_Candidates(int*L,int p,int r,int*&winner,stack<int*>&post_order);
void print_in_order(stack<int*>&post_order,int depth);

//L is continuous array starting from indices p to r inclusive
//returns Second Minimum ie. smallest loser (second min) to winner (min)
int*Second_Minimum(int*L,int p,int r){
int*winner=nullptr;
stack<int*>post_order;
int*second_minimum=Find_Candidates(L,p,r,winner,post_order);
print_in_order(post_order,0);
return second_minimum;
}

//post_order is solely for printing purpose
//returns pointer to second minimum or nullptr if it doesn't exist
int*Find_Candidates(int*L,int p,int r,int*&winner,stack<int*>&post_order){
//a single element must be winner
if(p==r){
winner=L+p;
post_order.push(nullptr);//left child
post_order.push(nullptr);//right child
post_order.push(winner);//this node
return nullptr;//no one lost to the winner
}
int q=(p+r)/2; //same as floor((p+r)/2), aka lower median
int*lt_smallest_loser=Find_Candidates(L,p,q,winner,post_order); //smallest loser to winner in left subtree
int*lt_winner=winner; //winner from left subtree
int*rt_smallest_loser=Find_Candidates(L,q+1,r,winner,post_order); //smallest loser to winner in right subtree
int*rt_winner=winner; //winner from right subtree

if(*lt_winner<*rt_winner){
winner=lt_winner;//rt_winner becomes a loser now
post_order.push(winner);
if(lt_smallest_loser!=nullptr&&
*lt_smallest_loser<*rt_winner){
return lt_smallest_loser;// still the smallest loser
}else
return rt_winner;// rt_winner becomes the smallest loser
}else{
winner=rt_winner;//lt_winner becomes a loser now
post_order.push(winner);
if(rt_smallest_loser!=nullptr&&
*rt_smallest_loser<*lt_winner){
return rt_smallest_loser;// still the smallest loser
}else
return lt_winner;// lt_winner becomes the smallest loser
}
}

void print_in_order(stack<int*>&post_order,int depth){
int*root=post_order.top();
post_order.pop();
if(root==nullptr)
return;
else{
//print right
print_in_order(post_order,depth+1);
for(int i=0;i<depth;++i)
cout<<'\t';//print tab
cout<<*root<<endl;
//print left
print_in_order(post_order,depth+1);
}
}

int main(){
int L[]{3,1,5,2,4};
int n=sizeof(L)/sizeof(int);
int*result=Second_Minimum(L,0,n-1);
cout<<"2nd smallest: ";
if(result!=nullptr)
cout<<*result<<endl;
else
cout<<"doesn't exist"<<endl;
}