Find 2nd largest number in an array with minimum comparisons
  • array
  • searching
  • noOfComparisons
  • Posted: 5 years ago
  • Updated: 4 years ago
  • Edit
  • answers (1)
  • views (12061)

Suppose you are given an unsorted array of n distinct elements where n is a power of 2 . How will you identify the second largest element with minimum number of comparisons?

Posted Answers

Total number of elements in the input array = \( n = 2^{k} \) (given)
Total number of comparisons to find the largest element
= \( n \times (\frac{1}{2^{1}}+\frac{1}{2^{2}}+\frac{1}{2^{3}}+\frac{1}{2^{i}}) \)
where i = height
= n-1 .

To find the second largest element we can start from the largest element (root) to the level above leaves following the path of the selection of the largest element. At each level, we will get those element(s) that were directly compared to the root and got rejected in the first round to find the largest element. The maximum of these elements (except the leaf level) will be the second largest element. Since the height is \( log_{2}n \) and we are not considering the leaf level at this round, total number of comparisons to find the second largest element = \( (n-1)+(log_{2}n-1)=n+log_{2}n-2 \).

Example- Let us assume the input array is [ 5 4 1 8 7 2 6 3 ]. We can find the largest and the second largest element by

You need to Sign In to post your solution.