Finding the second smallest number in an unordered list
Finding the second smallest element with the minimum number of comparisons:
Let’s assume that the unordered sequence contains n elements. Then we can find the smallest element in n-1 comparisons.
We can do this by having a variable (let’s call it ‘minNum’), and storing the first value in it. Then comparing the ‘minNum’ with every value in the list and keep replacing the value in the variable with the smallest number in each comparison.
We can also find the smallest by dividing the list into multiple pairs and comparing within them, then keep repeating until it leaves us with the smallest element (similar to merge sort). To keep the problem simple, let’s assume the number of elements in the array be a power of 2, (or n = 2ᵏ )
In the first step we would do n/2 comparisons, the next step n/4, then n/8, and 1 comparison in the last step.
Total comparisons => 𝑛/2+𝑛/4+…+𝑛/(𝑛/2)+𝑛/𝑛
T => 2(𝑛/4+𝑛/8+…+𝑛/(𝑛/2)+ 1) + 1
The value inside parenthesis is the same as T, except it misses n/2
Therefore, T => 2(𝑇− (𝑛/2)) + 1
Solving the equation,
T = 2T — n +1
T = n — 1
So n-1 comparisons to find the smallest element. Since the second smallest element will be smaller than only the smallest element, we would have definitely compared it with the smallest element before finding it. If we stored the values compared with every element in a map and now, we can search for the second smallest only by comparing the elements that we already compared with the smallest element.
Based on the above method, we will compare the smallest element with log(2)n elements, therefore the number of comparisons required to find second elements will be
T’ = log(2)n — 1
So Total comparisons => T +T’
n-1+ 𝑙𝑜𝑔2 n — 1
no 𝑙𝑜𝑔2n — 2
So we have designed an algorithm with the required comparisons in the worst case.
Another way to look at the problem
Let us consider a tournament. Assume that you have a list of n players (denoted by unique integers). One tournament rule could be that the smallest number of two numbers wins. Now, we can use the algorithm seen before to find out the smallest number in n — 1 comparisons. Realize that, in such a tournament, the smallest number (best player) is guaranteed to play the second smallest number (second best player), if we follow our rule. Therefore, once we have discovered the best player, we need to examine the sub-tree from where the best player originated. This is because the best player could have played the second-best player at any level in the tournament (and not just the final round). This analysis takes log2(n)−1 comparisons. Therefore, we have at most n+log2(n)−2 comparisons to find the second-best player in the tournament.
Using Min-Heap data structure
Another similar way to solve this to construct a min-heap. Construction of the min-heap would take O(n). This would entail that the minimum value in the sequence is present in the root. Remove the minimum and replace it with the rightmost element in the tree, following level order traversal. Heapify the new tree and you will have the second smallest element as the root now. Heapify takes O(log n) time. Hence the total time to find the second smallest element is less than n+log2(n)−2.