發現5個元素

Question

以下問題的中位數在最近的一次採訪微軟

給定大小5 的排序的數組有多少最小的比較需要找到中間有人問？然後他將它擴展爲n。根據我對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個元素。如果不是，我們怎麼能在O（n）中找到n個元素的中位數，除了快速選擇

Answer 1

Select算法將列表分成五個元素的組。 （現在忽略元素被忽略。）然後，對於每個五個組，計算中位數（如果五個值可以加載到寄存器並進行比較 - 最少6個比較，則可以非常快速地進行操作）。然後在這個n/5元素的子列表上遞歸調用Select，以找到它們的真正中位數。