следующий вопрос был задан в недавнем интервью Microsoft
Дан несортированный массив размера 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 элементов. если нет, как мы можем найти медиану в n элементах в O (n ), кроме быстрого выбора