[Algorytmy] Problem z medianą

[matexik]

Mamy ciąg \(\displaystyle{ N}\), który zawiera \(\displaystyle{ n}\) dowolnych liczb całkowitych, oraz funkcje \(\displaystyle{ f(x, y, z)}\), którą używamy tak, że podajemy indexy 3 liczb ciągu \(\displaystyle{ N}\), a ona zwraca index mediany tych 3 liczb. Jak za pomocą tylko tej funkcji można znaleźć index mediany całego ciągu \(\displaystyle{ N}\)?

[Afish]

Zakładam, że ciąg ma nieparzystą liczbę elementów i mediana jest dobrze zdefiniowana. Dla parzystej pewnie da się uogólnić, ale nie próbowałem.

Algorytm 1:
Zauważmy, że elementy najmniejszy i największy nigdy nie będą medianami, więc możemy takie elementy znaleźć i usunąć z ciągu, czym zmniejszymy rozmiar problemu. Zatem sprawdzamy wszystkie trójelementowe podzbiory ciągu i usuwamy dwa elementy, które nigdy nie były medianami.
Co w przypadku nieistnienia najmniejszego/największego elementu? Jeżeli mamy remis na pozycji minimum/maksimum, to nas to nie boli, bo wtedy wystarczy usunąć te dwa elementy, które najrzadziej były medianami.
Złożoność to \(\displaystyle{ O \left( n\left(n \choose 3\right) \right)}\).

Algorytm 2:
Na oko poprzedni algorytm da się ulepszyć tak, aby tylko raz sprawdzić wszystkie podzbiory trójelementowe i jako medianę wskazać ten element, który był medianą największej liczby podzbiorów. Dowód na oko powinien iść przez indukcję względem liczby elementów ciągu.

[matexik]

Tak, zapomniałem dodać, że ciąg \(\displaystyle{ N}\) ma nieparzystą ilość elementów. Zastanawiam się tylko jak rozwiązać to zadanie w złożoności \(\displaystyle{ O \left( \log n \right)}\) lub \(\displaystyle{ O \left( n \right)}\).

[Afish]

Logarytmicznie się nie da, liniowo może da się przerobić magiczne piątki.