Алгоритм медианы медиан - какой элемент выбрать в качестве медианы для каждой группы

Question

(ПРИМЕЧАНИЕ. Я делю массив на подмассивы, содержащие 5 элементов в моем примере)

Я понимаю, что алгоритмы медианы медиан разбивают массив n-входов на этаж (n / 5 ) групп с дополнительными содержащими группу (n) элементами mod5, а затем находит медианный элемент каждой отсортированной группы (3-й элемент в группах по 5 элементов) и т. д.

У меня вопрос, если один из в группах было 2 или 4 элемента, причем этот элемент был бы выбран в качестве медианы этой группы (при условии, что группа уже отсортирована).

Answer 1

Для группы из 2 элементов будет выбрано самое левое значение в отсортированной группе.

, например, для группы

[2,5]

2. в качестве медианы группы.

Для группы из 4 элементов 2-й элемент будет медианой.

Для обобщения этого медиана в группе с четным числом элементов будет левая медиана (согласно большинству примеров в книгах и онлайн). Тем не менее, совершенно правильно выбрать правильную медиану в четном списке, если эта стратегия используется последовательно в алгоритме.