ढूँढने 5 तत्वों

Question

निम्नलिखित प्रश्न की औसत हाल ही में एक साक्षात्कार माइक्रोसॉफ्ट

आकार 5. का एक अवर्गीकृत सरणी कितने न्यूनतम तुलना मंझला खोजने के लिए की जरूरत है यह देखते हुए में पूछा गया था? फिर उसने इसे आकार एन के लिए बढ़ा दिया। मेरे हिसाब से 5 तत्वों के लिए

समाधान 6

1) use 3 comparisons to arrange elements in array such that a[1]<a[2] , a[4]<a[5] and a[1]<a[4] 
a) compare a[1] and a[2] and swap if necessary 
b) compare a[4] and a[5] and swap if necessary 
c) compare a[1] and a[4].if a[4] is smaller than a[1] , then swap a[1] wid a[4] and a[2] wid a[5] 
2)if a[3]>a[2].if a[2]<a[4] median value = min(a[3],a[4]) else median value=min(a[2],a[5]) 
3)if a[3]<a[2].if a[3]>a[4] median value = min(a[3],a[5]) else median value=min(a[2],a[4]) 

इस n तत्वों लिए बढ़ाया जा सकता है। यदि नहीं, तो हम ओ (एन) में एन तत्वों में मध्यस्थ कैसे प्राप्त कर सकते हैं, इसके अलावा

Answer 1

चयन करें एल्गोरिदम सूची को पांच तत्वों के समूहों में विभाजित करता है। (अब तत्वों के ऊपर छोड़ दिया गया है।) फिर, पांच के प्रत्येक समूह के लिए, औसत की गणना की जाती है (एक ऑपरेशन जिसे संभावित रूप से बहुत तेज़ बनाया जा सकता है यदि पांच मान रजिस्टरों में लोड किए जा सकते हैं और तुलना की जाती है - 6 तुलना मिनट)। फिर अपने असली औसत को खोजने के लिए एन/5 तत्वों के इस उपन्यास पर चयन को फिर से कहा जाता है।