/* ZADANIE:

Napisz szablon funkcji, która na wejściu otrzyma kolekcję elementów
i zwróci wartość środkowego elementu (medianę). 

Uwagi:
* Można założyć, że kolekcja zawiera przynajmniej jeden element
* Można założyć, że kolekcja posiada funkcje begin() i end() zwracające iteratory
* W rozwiązaniu nie można użyć pętli ani std::for_each.
* Funkcja może zmodyfikować kolejność elementów w kolekcji jako efekt uboczny
  swojego działania.
* Funkcja ma działać dla różnych typów danych, tzn. możemy do niej podać zarówno
  np. wektor intów jak i ciąg znaków.
* Złożoność rozwiązania ma być amortyzowana liniowa (std::sort się nie kwalifikuje)

*/

// rozwiązanie

#include <algorithm>

template<typename T>
auto median(T collection) {
    const auto size = std::distance(collection.begin(), collection.end());
    const auto middle = collection.begin() + size/2;
    std::nth_element(collection.begin(), middle, collection.end());
    return *middle;
}

// przykład wywołania (możesz im podać)

#include <vector>
#include <string>
#include <print>

int main() {
    auto vec = std::vector{6, 6, 6, 1, 1, 1, 4};
    std::println("{}", median(vec));
    std::println("{}", median(std::string{"Alamakota"}));    
}