Wydajny sposób, aby uzyskać środkową (medianę) std :: set?

Question

std::set to posortowane drzewo. Udostępnia metody begin i end, więc mogę uzyskać minimum i maksimum oraz lower_bound i upper_bound dla wyszukiwania binarnego. Ale co jeśli chcę, aby iterator wskazywał środkowy element (lub jeden z nich, jeśli jest tam nawet liczba elementów)?

Czy jest to skuteczny sposób (O(log(size)), nie O(size)), aby to zrobić?

{1} => 1 
{1,2} => 1 or 2 
{1,2,3} => 2 
{1,2,3,4} => 2 or 3 (but in the same direction from middle as for {1,2}) 
{1,312,10000,14000,152333} => 10000 

PS: Same question in Russian.

Answer 1

W zależności od tego, jak często wstawić/usunąć elementy kontra spojrzeć w górę środkowy/mediana, możliwie bardziej efektywne rozwiązanie niż oczywistym rozwiązaniem jest utrzymać trwałe iterator do środkowy element i aktualizuj go za każdym razem, gdy wstawiasz/usuniesz elementy z zestawu. Istnieje kilka skrajnych przypadków, które będą wymagały obsługi (nieparzysta, a nawet liczba elementów, usunięcie środkowego elementu, pustego zestawu itp.), Ale podstawową ideą byłoby, aby wstawić element mniejszy niż bieżący środkowy element , twój środkowy iterator może wymagać zmniejszenia, a jeśli wstawisz większy, musisz zwiększyć. W przypadku przeprowadzek jest na odwrót.

W czasie wyszukiwania jest to oczywiście O (1), ale ma również zasadniczo koszt O (1) przy każdym wstawieniu/usunięciu, tj. O (N) po N wstawieniach, które muszą zostać zamortyzowane na wystarczająca liczba wyszukiwań, aby była bardziej wydajna niż brutalne wymuszanie.

Answer 2

To będzie O (rozmiaru), aby uzyskać środek poszukiwania binarnego drzewa. Można go pobrać z std::advance() następująco:

std::set<int>::iterator it = s.begin(); 
std::advance(it, s.size()/2); 

Answer 3

Jeśli dane jest statyczna, te, które mogłyby go precalcate i nie wstawić nowe elementy - to prostsze w użyciu wektora, sortować, a mediana dostęp tylko przez indeks w czasie O (1)

vector<int> data; 
// fill data 
std::sort(data.begin(), data.end()); 
auto median = data[data.size()/2];