Finding the second element neither minimum nor maximum

Question

How many comparisons are there for finding any second element that is neither minimum or maximum.

10  5  50  70  80  2  3

Comments

what is meaning of 2nd element .

if we sort array in ascending order , 2,3,5,10,50,70,80 , from left 5 is 2nd element which is neither max or min but if sort it in descending order 80,70,50,10,5,3,2 then from left , 50 is 2nd element which is neither max or minimum.

can u provide more detail explanation for ur question?

---

http://www.geeksforgeeks.org/gate-gate-cs-2015-set-2-question-32/

---

any second element that is neither a min nor max.

Answer 1

• take first five element and sort them 
• pick tne 3rd element which is 2nd nither maximam nor minimam .
• it will takeO(nlogn) time

SO total comprasons = 5log5= 12 comprasons.

Answer 2

Take any 3elements. Compare them with each other. It will take exactly 3comparisons.

The element which is neither highest nor the lowest of the three picked is your number.

So in constant time you can do this. Precisely 3comparisons only

Answer 3

best way is,

build heap(either max or min)..it will take 8 comparisons...now A[0] will be maximum and A[1] will be neither max nor min..

hence total '8' comparisons...

Comments

if we can just find out the middle element in the sorted array

suppose sorted array is 2,3,5,10,50,70,80 and middle is 5 and it's neither max nor min.

if we find 2 max and 2 minimum OR if we find the 3rd minimum so 3rd minimum is neither the first 2 minimums and nor the last 2 maximums.

Please throw some light.

---

ohh sorry, it can be done by taking any 3 elements and compare among them..

---

i think we should consider first five elements because in worst case it could contain 2 minimum's and 2 maximum's and the left element would be the desired one...

if we do so ....taking first five 10  5  50  70  80 then how many comparisons amongst them to find out that 50 is the desired element?