Можем ли мы доказать, что алгоритм извлечения медианы должен разбивать множество?

Question

Извлечение медианы, скажем, из 51 элемента состоит из разбиения 51 на группу H(ead) из 25, за которой следует медиана, за которой следует T (ail) из 25. Все известные мне алгоритмы заканчиваются на дополнительное свойство в том, что H и T таковы, что [min(H), max(H)[и]min(T), max(T)] не перекрываются.

Является ли это дополнительное свойство доказанным обязательным (думаю, да)? где я могу найти доказательства (я думаю, это было сделано давно)?

(Это только ради любви к алгоритмам)

Answer 1

Если элементы не являются уникальными, то эти два набора могут фактически перекрываться (представьте список из 51 идентичных элементов....)

Если элементы уникальны, то неперекрывающееся свойство легко доказать противоречием. Из разделения уникальных элементов мы имеем:

• х <медиана для всех х в H
• y > медиана для всех y в H

Предположим, что H и T перекрываются. Тогда мы имеем:

• x>= y для некоторого x=max(H), y=min(T)

Но это подразумевает:

• х>= у> медиана

Что является ограничением, потому что мы уже знаем х <медиана. Следовательно, два набора не могут перекрываться.