Given an array of \(N\) elements, return the second maximum/minimum elements using minimum number of comparison. A standard way for this task is to apply a tree and keep track of a list of compared items.
However, it is important to realize that this optimal is achieved only when the elements are distinct. Otherwise, one can end up comparing an extra half of the whole array.
For example, to locate the second minimum of the following array:
- \(\left[1,2,1,3,1,4,1,5\right]\)
- \(\left[1,3,1,2,1,4,1,5\right]\)
- \(\left[1,3,1,5,1,4,1,2\right]\)
One cannot drop a subtree when the children are equal.